什么是 Manacher 算法？

Manacher 算法是一种用于在 线性时间内 找到字符串中最长回文子串的算法。传统的中心扩展法时间复杂度为 O(n²)，而 Manacher 算法通过利用回文串的对称性，避免了大量重复的比较，达到了 O(n) 的效率。

核心思想

Manacher 算法的核心在于维护一个 回文半径数组 p 和两个变量：

• p[i]: 以字符 i 为中心的回文串的半径长度。
• max_right: 当前已发现的所有回文串中，右边界能到达的最远位置。
• center: 对应 max_right 的那个回文串的中心位置。