FROM: http://hi.baidu.com/chenwenwen0210/item/482c84396476f0e02f8ec230
#include<stdio.h>#include<math.h>#include<string.h>#include<map>#include<algorithm>#include<queue>using namespace std;
typedef __int64 lld;
const int MAX=1100000*2;
char str[MAX];//原字符串
char sb[MAX];
int p[MAX];//表示以i为中心的回文半径，
/*p[i]-1刚好是原字符串以第i个为中心的回文串长度。画画图就知道了，因为两端配匹的肯定是字符g*//*Mancher主算法。功能：求出以i为中心的回文半径p[i];参数：传入构造好的字符串长度特殊说明：因为前面加了一个无效字符，所以下标从1开始。 */void Manacher(int n)
{ int i;
int mx=0;//记录前面回文串最长影响到的地方。不一定是最长回文串造成的。
int id;//最长影响串的ID;
p[0]=0;
for(i=1;i<n;i++)
{
p[i]=1;//至少是1
if(mx>i)//i受到影响即，id+p[id]-1>=i;
{
p[i]=p[2*id-i];//2*id-i是i关于id的对称点相当于是id-(i-id);
if(mx-i<p[i])p[i]=mx-i;
//由于对称点的回文半径可能超过mx-i,因为mx后面的还没有配过
//所以要取小的。等等继续配
}
//向两端配匹
while(str[i-p[i]]==str[i+p[i]])p[i]++;
if(i+p[i]>mx)
{
mx=i+p[i];
id=i;
}
}
} /*功能：构造字符串，在每一个字符前插入一个，g,一般用'#'第一个字符前面再插入,first,一般用'$'最后再插入g字符总之不是在输入中出现的字符就行了。比如abb,构造成$#a#b#b#参数：<first,第一个字符>，<g,一般字符> 返回值：构造好的字符串长度*/int pre(char first='$',char g='#')
{ int i,n=0;
strcpy(sb,str);
str[0]=first;
n++;
for(i=0;sb[i];i++)
{
str[n++]=g;
str[n++]=sb[i];
}
str[n++]=g;
str[n]=0;
return n;
}int main()
{ int n;
int i;
int CS=1;
while(scanf("%s",str)!=EOF)
{
if(strcmp(str,"END")==0)break;
n=pre();
Manacher(n);
int ans=0;
for(i=1;i<n;i++)
{
if(p[i]>ans)ans=p[i];
}
printf("%d\n",ans-1);
}
return 0;
}