POJ 3974 Manacher算法（模板）

Manacher模板题

//By SiriusRen
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 2005000
int l,mx,p[N],id,ans,cases;
char a[N],b[N];
int main(){
    while(scanf("%s",a+1)&&strcmp(a+1,"END")){
        l=strlen(a+1);
        for(int i=1;i<=l;i++)b[i<<1]=a[i],b[i*2-1]='#';
        b[0]='&',b[l*2+2]='$',b[l<<1|1]='#';
        for(int i=1;i<=l*2+2;i++){
            if(mx>i)p[i]=min(p[id*2-i],p[id]+id-i);
            else p[i]=1;
            while(b[i-p[i]]==b[i+p[i]])p[i]++;
            if(i+p[i]>mx)mx=i+p[i],id=i;
            ans=max(ans,p[i]);
        }
        printf("Case %d: %d
",++cases,ans-1);
        memset(p,0,sizeof(p)),mx=id=ans=0;
    }
}