Manacher

2huk · 2025-06-24 17:19:34 · 算法·理论

前情提要 Z-Algorithm。这两个东西真得的很像。没错我大部分都是复制的。

默认字符串为 s，长度为 n，从 0 下标。s[l, r] 表示 s 中下标在 l \sim r 的字串。

Manacher 和扩展 KMP 在原理上极为相似。Manacher 所解决的问题是，求解 p_i 数组，表示以 i 为中心的最长回文半径。即 p_i 满足 s[i-p_i+1,i+p_i-1] 是回文串且 p_i 最大。

显然可以通过二分+哈希在 \mathcal O(n \log n) 的复杂度内轻松解决，但其并没有正确性保障，且复杂度偏高。而 Manacher 可以在线性时间复杂度内解决这个问题，且代码复杂度并不复杂许多。

接下来介绍这个算法的流程。

我们按照从前往后的顺序递推地求出 p_i，即我们默认 p_0 \dots p_{i-1} 均已求解。

我们维护 r,k，表示 i 之前的右端点最大的回文子串的左右端点。即 r 为 j \in [0, i-1] 中最大的 i + p_j-1，这个 j 为 k。初始 r=k=-1。

此时显然有 l \le i。我们讨论 i 与 r 的关系。

•  此时 $i$ 可以继承 $2k-i$ 的信息，因为它们都在 $[k-p_k+1,k+p_k-1]$ 这个回文子串中且位置对称。 - $p_{2k-i} \ge r-i+1$：从 $r-i+1$ 开始，继续暴力扩展； - 否则：$p_i = p_{2k-i}$。

每次暴力扩展后，r 都会变大（或不变），所以复杂度是 \mathcal O(n) 的。

for (int r = -1, k = 0, i = 0; i < n; ++ i ) {
    if (r >= p[2 * k - i] + i) {
        p[i] = p[2 * k - i];
    } else {
        p[i] = min(r - i + 1, p[2 * k - i]);
        while (i + p[i] < n && i - p[i] >= 0 && s[i - p[i]] == s[i + p[i]]) {
            p[i] ++ ;
        }
    }

    if (i + p[i] - 1 > r) {
        k = i;
        r = i + p[i] - 1;
    }
}