1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
| #include <iostream> #include <cstring> #include <cstdio>
using namespace std; char s[11000110],s2[33000300]; int p[33000300]; int init(){ int len=strlen(s); s2[0]='%'; s2[1]='#'; int j=2; for(int i=0;i<len;i++){ s2[j++]=s[i]; s2[j++]='#'; } s2[j]='*'; return j; } int manacher(){ int len=init(); int maxLen=-1; int 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; while(s2[i-p[i]]==s2[i+p[i]]) p[i]++; if(mx<i+p[i]) id=i,mx=i+p[i]; maxLen=max(maxLen,p[i]-1); } return maxLen; } int main(){ gets(s); printf("%d",manacher()); return 0; }
|