容斥刷不动啊！！今天十分的邪恶加猥琐的注册了一个小号和大一的孩子们一起做题；
也没有要和他们比赛的意思，只是我对算法有很多不熟悉的，所以呢....哎 我的号交几个题，小号交几个题。
做都做了，不管了。
晚上花了一个半小时才看懂的一个算法Manacher,专门用来做回文的....
网上其他的人写得佷详细了，我还是说说自己的吧。
Manacher利用了回文的性质。
假设有一个回文以id为中点，p[id]是这个回文的半径。
那么id右边的点i,若点i在id控制的回文串的范围内。
则i关于id对称的点j,通过几何性质可得出j=id*2-i;
则以j为中点的回文串的左边界若处于id回文串的左边界以内。
则由回文的性质可得知p[i]与p[j]是等价的。
因为以j为中心的字符串完全在id的回文串内，若j所决定的回文串超出了id的左边界.
那么以i为中心的字符串最长为mx-i，也就是i离mx的距离为p[i],i的回文长度。
做完这一步再由i向左右拓展，使得回文串增长。
这样达到的最右边mx进行更新。
大体的算法就是这样了：
#include<iostream>
#include<cstdio>
#include<string.h>
using namespace std;int p[2222222];
char str[1111111],str1[2222222];
int len;void Init()
{str1[0]='$';str1[1]='#';len=2;for( int i=0;str[i]!=0;i++ ){str1[len++]=str[i];str1[len++]='#';}str1[len]=0;
}int main()
{int T=0;while( scanf("%s",&str)!=EOF ){if( strlen(str)==3 && str[0]=='E' && str[1]=='N' && str[2]=='D' )break;//memset( str1,0,sizeof(str1) );memset( p,0,sizeof(p) );Init();int id,mx=0;for( int i=1;i<len;i++ ){if( mx>i )p[i]=min(p[(id<<1)-i],mx-i);elsep[i]=1;while( str1[i-p[i]]==str1[i+p[i]] )p[i]++;if( mx<i+p[i] );{mx=i+p[i];id=i;}}printf( "Case %d: ",++T );int ans=0;for( int i=1;i<len;i++ )ans=max(p[i],ans);printf( "%d\n",ans-1 );}return 0;
}