Poj 3974 回文串--Manacher

//最长回文  
#include   
#include   
#include   
  
using namespace std;  
  
const int maxn = 1000000 + 10;  
  
char Ma[maxn*2];  
int Mp[maxn*2];  
  
void Manacher(char s[],int len)  
{  
    int l=0;  
    Ma[l++]='$';  
    Ma[l++]='#';  
    for(int i=0;ii min(Mp[2*id-i],mx-i):1;  
        while(Ma[i+Mp[i]]==Ma[i-Mp[i]]) Mp[i]++;  
        if(i+Mp[i]>





mx)  
        {  
            mx=i+Mp[i];  
            id=i;  
        }  
    }  
}  
  
char s[maxn];  
  
int main()  
{  
    int cnt=1;  
    while(~scanf("%s",s))  
    {  
        if(strcmp(s,"END")==0) break;  
        int len=strlen(s);  
        Manacher(s,len);  
        int ans=0;  
        for(int i=0;i<2*len+2;i++)  
            ans=max(ans,Mp[i]-1);  
        printf("Case %d: %d\n",cnt++,ans);  
    }  
    return 0;  
}