求最长回文串，如果是暴力的方法的话，会枚举每个字符为中心，然后向两边检测求出最长的回文串，时间复杂度在最坏的情况下就是0(n^2)，为什么时间复杂度会这么高，因为对于每一个作为中心的字符的检测是独立的，没有充分利用前面比较过信息，这就类似暴力求字符串的匹配最糟糕的情况下是0(n*m),然后通过预处理的信息把时间复杂度降低也就是kmp算法；
MANACHER算法:
先假设所有回文串都是以某个字符为中心的，即回文串的长度都是奇数；
lc[ i ]保存的是以位置i的字符为中心的最长回文串到最右边的距离
先假设以知lc[i]，(0<=i<x)求lc[x]
设p=k+lc[k]-1，k是使p最大的i的取值，如下图
如果x>p那么直接以x为中心进行检测，并更新k;
如果x<=p那么对于以k为中心x的对称点就是j，并且lc[j]的值已经知道了，
If (lc[j]<p-x+1) lc[x]=lc[j]
因为s[j-1]!=s[j+1], s[j-1]=s[x-1],s[j+1]=s[x+1]，所以s[x-1]!=s[x+1]如图：
If (lc[j]>=p-x+1) 那么lc[x]至少是lc[j] 如图：
但对于蓝色位置是不是还需要检测
时间复杂度分析：因为对于每一位s[i]都只被检测了一次，所以是o(n);
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
现在回到最原先的问题，因为回文串有可能是“1221”这种长度是偶数的，MANACHER算法提供了一个构造的方法可以统一这两种情况：在两个字符之间插入一个没有出现过的字符，如‘#’，那么”1221”->”#1#2#2#1#”这样所有的回文串长度都是奇数的了，为了处理方便再在该字符串前面加一个‘$’字符，这样字符串就是$#1#2#2#1#
求出lc[i]后，对于以s[i]为中心的字符串，如果s[i]==’#’,那么len=(lc[i]-1)/2*2,因为lc[i]-1肯定是偶数（因为该回文串的最左和最右肯定是’#’）所以len=lc[i]-1;
如果s[i]!=’#’,那么len=(lc[i] - 1)/2*2+1;因为lc[i]-1肯定是奇数，所以len=lc[i]-2+1=lc[i]-1;
所以最后的解就是最大lc[i]-1；
void Manacher(char *s){
s1[]='$';
int nn=strlen(s),c=;
for (int i=;i<nn;i++){
s1[c++]='#';
s1[c++]=s[i];
}s1[c++]='#';s1[c++]='\0';
// cout<<s<<endl<<s1<<endl;
lc[]=;lc[]=;
int k=, p, j;
for (int i=;i<c;i++){
p=k+lc[k]-;
if (p<i){
int t=;
while (i-t>= && i+t<c && s1[i-t]==s1[i+t]) t++;
lc[i]=t; k=i;
}else {
j=*k-i;
if (lc[j]<p-i+) lc[i]=lc[j];
else {
int t=p-i+;
while (i-t>= && i+t<c && s1[i-t]==s1[i+t]) t++;
lc[i]=t; k=i;
}
}
}
int ret=;
for (int i=;i<c;i++){
//cout<<lc[i]<<" ";
if (lc[i]->ret) ret=lc[i]-;
}//cout<<endl;
printf("%d\n",ret);
}