功能：
在线性时间复杂度内求解以每个字符为中心(奇数）或者偶数符间隙为中心的回文串长度。
p[]中存储每个下标对应的字符为中心的回文串长度 str[]存储塞入添加字符后的字符串 s[]为原始输入字符串
原理可以看此篇博客
#include<bits/stdc++.h> using namespace std; const int maxn=3e5; char s[maxn]; char str[maxn]; int p[maxn],len2,len1; void init() { len1=strlen(s); str[0]='@'; for(int i=1;i<=2*len1;i+=2) { str[i]='#'; str[i+1]=s[i/2]; } str[2*len1+1]='#'; str[2*len1+2]='$'; str[2*len1+3]=0; len2=2*len1+1; } int manacher() { int mx=0,ans=0,po=0; for(int i=1;i<=len2;i++) { if(mx>i) p[i]=min(mx-i,p[2*po-i]); else p[i]=1; for(;str[i-p[i]]==str[i+p[i]];p[i]++) if(p[i]+i>mx) { mx=p[i]+i; po=i; } ans=max(ans,p[i]); } return ans-1; } int main() { while(~scanf("%s",s)) { init(); printf("%d\n",manacher()); } return 0; }杭电3068
