HDU 3294 Girl's research(最长回文子串)

// // main.cpp // Richard // // Created by 邵金杰 on 16/9/27. // Copyright © 2016年 邵金杰. All rights reserved. // #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn=200000+100; char s[maxn*2]; int p[maxn*2]; int main() { char c; while(scanf("%c %s",&c,s)!=EOF) { int len=(int)strlen(s); for(int i=len;i>=0;i--){ s[i+i+2]=s[i]; s[i+i+1]='#'; } s[0]='*'; int id=0,maxlen=0,pos=0; for(int i=2;i<2*len+1;i++) { if(p[id]+id>p[i]+i) p[i]=min(p[id*2-i],p[id]+id-i); else p[i]=1; while(s[i+p[i]]==s[i-p[i]]) p[i]++; if(p[i]+i>p[id]+id) id=i; if(maxlen<p[i]) {maxlen=p[i];pos=i;} } if(maxlen-1==1) {printf("No solution!\n");continue;} int x='a'-c; cout<<(pos-maxlen+1+1)/2-1<<" "<<(pos+maxlen-1-1)/2-1<<endl; for(int i=(pos-maxlen+1+1);i<=(pos+maxlen-1-1);i++) if(s[i]!='#') printf("%c",((s[i]+x)>='a')?(s[i]+x):(s[i]+x+26));printf("\n"); getchar(); } return 0; }