Palindrome
求最长回文字串。
manacher模板题。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 const int maxn=1000010; 6 char s[maxn<<1]; 7 int r[maxn<<1]; 8 9 int main(){ 10 int cas=0; 11 while(scanf("%s",s)){ 12 if(strcmp(s,"END")==0) return 0; 13 else{ 14 int n=strlen(s); 15 for(int i=n;i>=0;i--){ 16 s[i*2+2]=s[i]; 17 s[i*2+1]='#'; 18 } 19 s[0]='*'; 20 int id=0,m=0; 21 for(int i=2;i<n*2+1;i++){ 22 if(id+r[id]>i) r[i]=min(r[id*2-i],r[id]+id-i); 23 else r[i]=1; 24 while(s[i-r[i]]==s[i+r[i]]) r[i]++; 25 if(id+r[id]<i+r[i]) id=i; 26 if(m<r[id]) m=r[id]; 27 } 28 printf("Case %d: %d ",++cas,--m); 29 } 30 } 31 }