Manacher算法用于求回文子串，它的复杂度为O(n)。
这个算法有一个很巧妙的地方，它把奇数的回文串和偶数的回文串统一起来考虑了。在相邻的两个字符之间加进一个分隔符 '#' ，串的首尾也要加。
原串：abaab
新串：#a#b#a#a#b#
中心思想是，用一个辅助数组p记录以每个字符为中心的最长回文半径，也就是p[i]记录以s[i]字符为中心的最长回文半径。p[i]最小为1，此时回文串为s[i]本身。
我们用MaxId记录在 i 之前的回文串中，延伸至最右端的位置，同时用id记录这个MaxId的id值。核心代码如下：
for(i=;i<n;i++)
{
if(MaxId>i)
{
p[i]=min(p[id*-i],MaxId-i);
}
else
{
p[i]=;
}
while(a[i+p[i]]==a[i-p[i]])
{
p[i]++;
}
if(p[i]+i>MaxId)
{
MaxId=p[i]+i;
id=i;
}
｝
为了防止求P[i]向两边扩展时可能数组越界，我们需要在数组最前面和最后面加一个特殊字符，令P[0]=‘$’最后位置默认为‘\0’不需要特殊处理。