https://segmentfault.com/a/1190000008484167?tdsourcetag=s_pctim_aiomsg 讲的超好！
manacher算法理解
回文串分为偶回文串和奇回文串，由于偶回文串无法找到中点，所以这里将偶回文串转换为奇回文
转换方法s="abcde"=>s="$#a#b#c#d#e#"
数组p[i]，表示以i为中心的最长回文的半径，p[i]-1刚好是以i为中心的源字符串中的回文长度
从左往右扫描s，求出p数组
mx:延伸到最右边的回文的边界(不包含 )
id:mx对应的中点
现在扫到了i，i关于id对称点是j，p[j]已知，以下分三种种情况
1.i<mx:p[i]=min(p[j],mx-i)，i在mx左边
2.i>=mx:p[i]=1 ，i在mx的右边
3.往两边拓展边界
求出p[i]后更新mx即可
为什么复杂度是on？
当且仅当j的边界和mx重合时，i才要向两边扩展，
#include<bits/stdc++.h> using namespace std; #define maxn 100005 char s[maxn],s_new[maxn]; int p[maxn]; int init(){ int len=strlen(s); s_new[0]='$',s_new[1]='#'; int j=2; for(int i=0;i<len;i++) s_new[j++]=s[i],s_new[j++]='#'; s_new[j]=' '; return j; } int manacher(){ int len=init(); int res=0,id,mx=0; for(int i=1;i<len;i++){ if(i<mx) p[i]=min(p[2*id-i],mx-i); else p[i]=1; //当且仅当边界处于mx的时候(两边的匹配状况未知)，才会进入循环 while(s_new[i-p[i]]==s_new[i+p[i]]) p[i]++; if(mx<i+p[i]) mx=i+p[i],id=i; res=max(res,p[i]-1); } return res; } int main(){ cin>>s; cout<<manacher(); }
poj3974
#include<iostream> #include<cstring> #include<cstdio> using namespace std; #define maxn 3000005 int p[maxn],tt; char s[maxn],s_new[maxn]; int init(){ int len=strlen(s); s_new[0]='$',s_new[1]='#';int j=2; for(int i=0;i<len;i++) s_new[j++]=s[i],s_new[j++]='#'; s_new[j]=0; return j; } int manacher(){ int len=init(); int mx=0,id,res=0; for(int i=0;i<len;i++){ if(i<mx)p[i]=min(p[2*id-i],mx-i); else p[i]=1; while(s_new[i+p[i]]==s_new[i-p[i]])p[i]++; if(i+p[i]>mx) mx=i+p[i],id=i; res=max(res,p[i]-1); } return res; } int main(){ while(scanf("%s",s)){ if(s[0]=='E')break; memset(p,0,sizeof p); printf("Case %d: %d ",++tt,manacher()); } }