本文共 455 字，大约阅读时间需要 1 分钟。

预处理：

将字符串每个位置插入特殊符号“#”，例如“abba”为“#a#b#b#a#”，这样每个偶数或奇数回文串都被处理成了奇数回文串。

---

Manacher算法核心思想：

利用之前回文串的信息来提供当前串的先验信息。

需要维护2两个变量和一个数组：

变量R代表已经发现的所有回文串中可以到达最右的那个回文串的右边界，

变量Center代表满足上述条件回文串的对称中心位置， Parr[i]代表以i为中心的最大回文半径。

---

如何快速得到Parr[i]？

若R<=i，表明当前位置超过之前所有检查过回文串的右边界，所以没有先验信息可以提供，只能暴力检查以 i 为中心的最大回文半径，然后更新R和Center。

若R>i，表明之前的回文串已经检查过当前位置，所以可以利用对称信息来直接给出 以 i 为中心的最小回文半径，即Parr[i] 至少为 min{ Parr[Center*2-i] , R - i } , 然后直接从最小回文半径往外扩，最大的时间优化就是这个处理。

因为计算过程中R不断往右扩，所以时间为O(N)

---

转载地址：http://zdwji.baihongyu.com/