#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxn 2001000 using namespace std; char s[maxn],st[maxn]; int p[maxn]; int cases=1; int n; void rebuild() { st[0]='$'; st[1]='#'; int len=strlen(s); for(int i=0;i<len;i++) {st[2*i+2]=s[i];st[2*i+3]='#';} st[2*len+2]=0; } void solve() { int len=2*strlen(s)+2; int id,mx=0,ans=1; for(int i=0;i<len;i++) { if(mx>i) p[i]=min(p[2*id-i],mx-i); else p[i]=1; for(;st[p[i]+i]==st[i-p[i]];p[i]++) ; if(p[i]+i>mx) { mx=p[i]+i; id=i; } ans=max(ans,p[i]); } cout<<"Case "<<cases++<<": "<<ans-1<<endl; } int main() { while(gets(s)) { if(s[0]=='E'&&s[1]=='N'&&s[2]=='D') break; rebuild(); solve(); } return 0; }
poj_1974,最长回文字串manacher
时间复杂度为O(n),参考:http://bbs.dlut.edu.cn/bbstcon.php?board=Competition&gid=23474