如果一个字符串正着读和倒着读是一样的，则称它是回文的。
给定一个长度为N的字符串S，求他的最长回文子串的长度是多少。
输入将包含最多30个测试用例，每个测试用例占一行，以最多1000000个小写字符的形式给出。
输入以一个以字符串“END”（不包括引号）开头的行表示输入终止。
对于输入中的每个测试用例，输出测试用例编号和最大回文子串的长度（参考样例格式）。
每个输出占一行。
abcbabcbabcba
abacacbaaaab
END
Case 1: 13
Case 2: 6
题目：让你找出最长的回文子串
思路：
朴素算法 O(n^2)
枚举中点，然后分奇数长度串，偶数长度串，第二层循环来枚举长度是否可以
哈希做法 O(nlogn)，可优化为O（n）
我们知道哈希可以直接判断字符串是否相等，对于回文的情况我们可以正着求一遍哈希，然后反着再求一边哈希，我们就可以判断任意一个区间是否是回文串
只是我们不确定长度，这里我们可以照着上面的思路，枚举中点，然后二分长度，直接判断是否是回文串。
！！！注意，这里不同上面朴素做法的，上面是必须确定前面才能确定后面是否可以，所以长度必须从1开始遍历，所以我们其实可以省去二分，直接每到新的位置，我们直接从当前最大值+1开始枚举，这样
即时O（n）写法
马拉车算法 O（n）
还没学，菜鸡在此告辞
这里给上我写的哈希做法#include<bits/stdc++.h> #define maxn 1000005 #define mod 1000000007 using namespace std; typedef long long ll; typedef unsigned long long ull; char str[maxn]; ull dp1[maxn],f[maxn]; ull dp2[maxn]; ll len; void hash_code() { memset(f,0,sizeof(f)); memset(dp1,0,sizeof(dp1)); memset(dp2,0,sizeof(dp2)); len=strlen(str+1); f[0]=1; for(int i=1;i<=len;i++){ dp1[i]=dp1[i-1]*131+str[i]-‘a‘+1; f[i]=f[i-1]*131; } for(int i=len;i>=1;i--){ dp2[i]=dp2[i+1]*131+str[i]-‘a‘+1; } } int main(){ ll num=1; while(scanf("%s",str+1)!=EOF){ if(strcmp(str+1,"END")==0) break; hash_code(); /*int l,r; while(1) { cin>>l>>r; if(dp1[r]-dp1[l-1]*f[r-l+1]==dp2[l]-dp2[r+1]*f[r-l+1]){ cout<<"YES"<<endl; } else cout<<"NO"<<endl; }*/ ll mx1=0,mx2=0; for(int i=1;i<=len;i++){ for(int j=mx1+1;j<=len;j++){ if(i+j>len||i-j<=0) break; if(dp1[i+j]-dp1[i-j-1]*f[2*j+1]!=dp2[i-j]-dp2[i+j+1]*f[2*j+1]) break; mx1++; } for(int j=mx2+1;j<=len;j++){ if(i+j>len||i-j+1<=0) break; if(dp1[i+j]-dp1[i-j]*f[2*j]!=dp2[i-j+1]-dp2[i+j+1]*f[2*j]) break; mx2++; } //printf("%lld:%lld\n",i,mx1+1); } printf("Case %lld: %lld\n",num++,max(2*mx1+1,2*mx2)); } }
原文：https://www.cnblogs.com/Lis-/p/10891086.html