http://poj.org/problem?id=3974
模板题，Manacher算法主要利用了已匹配回文串的对称性，对前面已匹配的回文串进行利用，使时间复杂度从O(n^2)变为O(n)。
https://www.cnblogs.com/xiaoningmeng/p/5861154.html 详细解释
https://www.zhihu.com/question/30226229 这是复杂度O(n)的解释
代码
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<cmath> 5 #include<iostream> 6 #include<map> 7 #include<ctime> 8 using namespace std; 9 const int maxn=1000010; 10 char c[maxn]; 11 char s[maxn*2]; 12 int p[maxn*2]; 13 int len; 14 void init(){ 15 len=strlen(c); 16 int j=1; 17 s[0]='$';s[1]='#'; 18 for(int i=0;i<len;i++){ 19 s[++j]=c[i]; 20 s[++j]='#'; 21 }s[++j]=' '; 22 len=j; 23 } 24 int Manacher(){ 25 init();int ans=1; 26 int id,mx=0; 27 for(int i=1;i<len;i++){ 28 if(i<mx) p[i]=min(p[2*id-i],mx-i); 29 else p[i]=1; 30 while(s[i-p[i]]==s[i+p[i]]) 31 p[i]++; 32 if(mx<i+p[i]){ 33 id=i; 34 mx=i+p[i]; 35 } 36 ans=max(ans,p[i]); 37 } 38 return ans-1; 39 } 40 int main(){ 41 for(int i=1;;++i){ 42 scanf("%s",&c); 43 if(c[0]=='E')break; 44 printf("Case %d: %d ",i,Manacher()); 45 } 46 return 0; 47 }