Manache模板题

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int max_n = 1e6+100;

void Manacher(char s[],int d[],char ts[]){
    int n = strlen(s);
    fill(d,d+2*n+10,1);
    for (int i=0,j=0;i<n;++i){
        ts[j++]='#';ts[j++]=s[i];
    }n=n*2+1;ts[n]='\0';ts[n-1]='#';
    for (int i=0,j=-1,t=0;i<n;++i){
        if (j>=i)d[i]=min(j-i+1,d[(t<<1)-i]);
        while (i+d[i]<n&&i-d[i]>=0&&ts[i+d[i]]==ts[i-d[i]])++d[i];
        if (i+d[i]>j)j=i+d[i]-1,t=i;
    }
}

char s[max_n],ts[max_n<<1];
int d[max_n<<1];
int main(){
    int tcase=0;
    while (scanf("%s",s)){
        if (s[0]=='E')break;
        ++tcase;
        Manacher(s,d,ts);
        int n = strlen(ts);
        int ans = 1;
        for (int i=0;i<n;++i){
            ans = max(ans,((d[i]<<1)-1)>>1);
        }printf("Case %d: %d\n",tcase,ans);
    }
}