用于在线性时间内求出每个字符串的最长回文子串的算法。
首先需要把原串进行处理，使得所有的对称子串都是奇数长度的串。
代码如下：
/*
mx：能成为回文子串的最长的右边界
id：mx对应的对称中心
p[i]：某位置上字符的回文半径
ss为读入的字符串，s为处理后的字符串
*/
int manache()
{
s[0]='$';
int j=1;
for(int i=1;i<=n;++i)
{
s[j]='#';
j++;
s[j]=ss[i];
j++;
}
s[j]='#';
int l=j;
int mx=-inf,id,ans=-inf;
for(int i=1;i<=j;++i)
{
if(mx>i) p[i]=min(p[2*id-i],mx-i);
else p[i]=1;
while(s[i-p[i]]==s[i+p[i]]) p[i]++;
if(i+p[i]>mx)
mx=i+p[i],id=i;
ans=max(ans,p[i]-1);
}
return ans;
}