《算法竞赛进阶指南》 回文子串的最大长度

回文子串的最大长度

如果一个字符串正着读和倒着读是一样的，则称它是回文的。

给定一个长度为N的字符串S，求他的最长回文子串的长度是多少。

输入格式
输入将包含最多30个测试用例，每个测试用例占一行，以最多1000000个小写字符的形式给出。

输入以一个以字符串“END”（不包括引号）开头的行表示输入终止。

输出格式
对于输入中的每个测试用例，输出测试用例编号和最大回文子串的长度（参考样例格式）。

每个输出占一行。

输入样例：
abcbabcbabcba
abacacbaaaab
END
输出样例：
Case 1: 13
Case 2: 6

简单分析本题，这也是一个明显的哈希问题，还是让我们去找相同的字串，我们大的方向是将源字符串正序存储在一个数组、逆序存储在一个数组，这样在通过枚举每一位数据作为对称的中点再进行寻找当前点的最大半径，这样整体下来就能找到最大的回文子串。

下面我们以图形的方式举例，当在i位置时，怎样求左右对称的哈希值，假设此时的半径为mid：

上述做法由于我们假设有中点的存在，那么回文字串一定有奇数个，但肯定有偶数个回文字串的存在。这里我们的做法是在每一个小写字母中间添加一个特殊字符，把长度大概扩大一倍，这样就能解决了，可行性大家自己画图了解。

另外我们寻找当前位置的回文半径是用二分的方法做的，由于我们是填充了特殊字符后得到的半径，当我们半径的末尾是小写字母时回文字串的长度就是半径加1，否则就是半径。其原理大家自己画图了解

#include <iostream>
#include <string.h>
using namespace std;
const int N=2000010,base=131;
//根据分析原理我们要将字符串的长度扩大2倍
//并且哈希经验值取131
typedef unsigned long long ULL;
ULL hl[N],hr[N],p[N];
//分别存储正序、逆序、和131进制的数量级
char str[N];//存储源数据

ULL get(ULL h[], int l, int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];
}
int main()
{
	ios::sync_with_stdio(false);
	int T=1;
	while(cin>>(str+1),strcmp(str+1,"END"))
	{
		int n=strlen(str+1);
		n*=2;
		for(int i=n;i;i-=2)//将源数据进行扩展填充字符
		{
         str[i]=str[i/2];
         str[i-1]='z'+1;
		}
		p[0]=1;
		for(int i=1,j=n;i<=n;i++,j--)
		{//分别对源数据进行正序和逆序的哈希值计算和131进制的数量级计算
		 hl[i]=hl[i-1]*base+str[i]-'a'+1;
		 hr[i]=hr[i-1]*base+str[j]-'a'+1;	
         p[i]=p[i-1]*base;  
		}
		//通过把每个位置作为对称点的中心点来进行二分遍历半径
		int res=0;
		for(int i=1;i<=n;i++)
		{
			int l=0,r=min(i-1,n-i);//l、r为假设的当前位置对称半径的最小以及最大值
			while(l<r)
			{
				int mid=l+r+1>>1;//这里二分前加1，是因为我们下面有l=mid防止死循环
                //下面以半径为mid来半段对称字符串是否相同 
				if(get(hl,i-mid,i-1)!=get(hr,n-(i+mid)+1,n-i))r=mid-1;
				else l=mid;
			}
            if(str[i-l]<='z')res=max(res,l+1);
            else res=max(res,l);
		}
		printf("Case %d: %d\n",T++,res);
	}
	return 0;
}

本文地址：https://blog.csdn.net/qq_42635159/article/details/107572120