Palindrome

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 const int N=2e6+440;
 7 char str1[N],str[N<<1];
 8 int rad[N];
 9 char temp;
10 void Manacher(int *rad,char *str,int n){
11    int i,mx=0,id;
12    for(int i=1;i<n;i++){
13     if(mx>i){
14     rad[i]=min(rad[2*id-i],mx-i);
15    }
16    else
17     rad[i]=1;
18     for(;str[i-rad[i]]==str[i+rad[i]];rad[i]++){
19         if(rad[i]+i>mx){
20             mx=rad[i]+i;
21             id=i;
22         }
23      }
24    }
25 }
26 
27 int main(){
28     int cas=1;
29   while(~scanf("%s",str1)){
30        if(str1[0]==‘E‘)break;
31       int nn=strlen(str1);
32         int n=2*nn+2;
33         str[0]=‘$‘;
34       for(int i=0;i<=nn;i++){
35           str[2*i+1]=‘#‘;
36           str[2*i+2]=str1[i];
37       }
38       memset(rad,0,sizeof(rad));
39       Manacher(rad,str,n);
40       int ans=0;
41       for(int i=0;i<=n;i++){
42         if(rad[i]>=3&&rad[i]>ans){
43             ans=rad[i];
44         }
45       }
46       printf("Case %d: %d\n",cas++,ans-1);
47   }
48 }