Manacher 学习笔记

Manacher 可以在 $O(|S|)$ 的时间内求解以 $S$ 中每个位置作为回文中心时最长的回文半径．

Manacher 算法的流程如下：从 $1$ 到 $n$ 遍历整个串，记 $p_i$ 表示以位置 $i$ 为回文中心时的最长回文半径，设当前遍历到 $i$．在算法过程中，我们维护变量 $c$ 和 $r$，分别表示 $i$ 之前以任意字符为回文中心的回文串的最大右端点和取到这个值的位置．

现在考虑求解 $p_i$．若 $i \le r$，我们令 $p_i \leftarrow \min\{r - i + 1, p_{2c - i}\}$，由回文串的对称性，正确性显然；若 $i > r$，直接令 $p_i \leftarrow 1$．

在这些操作后，暴力扩展回文串．

看起来很暴力啊！为啥是对的呢？考虑每次迭代过程，若我们暴力扩展了，那么 $r$ 必定会至少向右边移动 $1$ 位，由于过程中 $r$ 单调不降，那么复杂度均摊 $O(n)$．