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);
}
}