原因:之前会这个算法,过了很久忘了。所以又得重新学习。如果留下自己的笔记，复习起来会很快。所以决定写一写自己的理解。
我学习Manacher看的是这一篇博客。
首先这个算法是解决最长回文子串问题的。
算法解释：将字符串之间插入同一个特殊字符，然后从前往后开始，p[i]数组代表以i为对称中心的字符串的长度（算上中心那个字符）。下面计算P[i]，该算法增加两个辅助变量id和mx，其中id表示最大回文子串中心的位置，mx则为id+P[id]，也就是最大回文子串的边界。
这个算法的关键点就在这里了：
如果mx > i，那么P[i] = MIN(P[2 * id - i], mx - i)。
后面的看代码注释：
/**
预先处理字符串,形如 $#a#b#a#b#
p[i]数组代表,以第i个字符串为对称中心的字符串最大对称数。
*/
void Manacher()
{
init();
int mx=0,id=1; //mx 为 右边界 , id 是对称中心
for(int i=1;i<len;i++)
{
if(mx>i) p[i]=min(p[2*id-i],mx-i);
else p[i]=1;
while(str[i+p[i]]==str[i-p[i]]) p[i]++;//检查p[i]是否还可以往两边扩展?
if(p[i]+i>mx)//如果当前状态右边界更远,则更新mx,id。
{
mx=p[i]+i;
id=i;
}
}
}