文档介绍：求回文子串 O(n) manacher 算法
回文串定义：“回文串”是一个正读和反读都一样的字符串，比如“level”或者“noon”
等等就是回文串。
回文子串，顾名 P[] : 1 2 1 4 1 2 5 2 1 2 1
我们可以证明 P[i]-1 就是以 Str[i]为中心的回文串在原串当中的长度。
证明：
1、显然 L=2*P[i]-1 即为新串中以 Str[i]为中心最长回文串长度。
2、以 Str[i]为中心的回文串一定是以#开头和结尾的，例如“#b#b#”或“#b#a#b#”
所以 L 减去最前或者最后的‘#’字符就是原串中长度的二倍，即原串长度为(L-1)/2，化简
的 P[i]-1。得证。
依次从前往后求得 P 数组就可以了，这里用到了 DP(动态规划)的思想，也就是求 P[i]
的时候，前面的 P[]值已经得到了，我们利用回文串的特殊性质可以进行一个大大的优化。
我先把核心代码贴上：
for(i=1;i<n;i++)
{
if(MaxId>i)
{
p[i]=Min(p[2*id-i],MaxId-i);
}
else
{
p[i]=1;
}
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’不需要特殊处理。此外，我们用 MaxId 变量
记录在求 i 之前的回文串中，延伸至最右端的位置，同时用 id 记录取这个 MaxId 的 id 值。
通过下面这句话，算法避免了很多没必要的重复匹配。
if(MaxId>i)
{
p[i]=Min(p[2*id-i],MaxId-i);
}
那么这句话是怎么得来的呢，其实就是利用了回文串的对称性，如下图，