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\n",++cases,ans-1);

        memset(p,0,sizeof(p)),mx=id=ans=0;

    }

}