俗话说：摩托再好，不如骡拉啊(好像不是骡）
Manacher就是O(N)计算最长回文子串的算法。
其中我们需要在0位置加入字符“$"，然后原字符串中每两个字符加入一个"#"。
算法中 id 为当前最长回文子串的中心 mx为当前最长回文子串的右侧位置。
每做到一个i，若mx>i，则p[i]=min(mx-i,p[2*id-i]),否则为1，然后暴力拓展。
证明什么的网上一大堆了。。
模板题：hdu3068
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<algorithm>
char s[],a[];
int p[];
int main(){
while (~scanf("%s",s)){
int len=,l1=strlen(s);
a[]='$';
for (int i=;i<l1;i++){
a[len++]='#';
a[len++]=s[i];
}
a[len]='#';
int mx=,id=;
memset(p,,sizeof p);
for (int i=;i<=len;i++){
if (mx>i){
p[i]=(mx-i<p[*id-i])?mx-i:p[*id-i];
}
else
p[i]=;
while (a[i-p[i]]==a[i+p[i]]) p[i]++;
if (i+p[i]>mx){
mx=i+p[i];
id=i;
}
}
int ans=;
for (int i=;i<=len;i++)
if (ans<p[i]) ans=p[i];
printf("%d\n",ans-);
}
}