Manacher 回文计数算法

以下假设字符串下标从 $0$ 开始，子串记号 $s[i..j]$ 左闭右闭。

给定长度为 $n$ 的字符串 $s$，Manacher 算法可以在 $O(n)$ 的时间复杂度内找到 $s$ 的所有回文子串。

我们先以寻找长度为奇数的子串为例。首先需要明确的是，如果 $s$ 中以第 $i$ 个字符为中心的最长回文子串长度为 $d=2p+1$，则以下皆为 $s$ 的回文子串：

$$s[i-(p-1)..i+(p-1)],\ldots, s[i-1..i+1], s[i..i]$$

因此，我们只需对所有下标 $i$ 求解出以 $s[i]$ 为中心的最长回文子串长度 $2p_i+1$，即可知道 $s$ 的所有回文子串。

Manacher 算法从左到右求解诸 $p_i$。在求解 $p_i$ 时，算法会保证诸 $p_0,\ldots,p_{i-1}$已经求解完毕，从而我们可以利用先前的信息合理减少计算。在这个过程中，我们将维护一个滚动的子串 $t=s[l..r]$，$t$ 是目前已探明的右端点最靠右的回文子串。如此一来，每次循环时，我们要考虑两种情况：

1. i 在子串 t 内，即 $l\leq i \leq r$。此时我们考虑 $i$ 在 $t$ 内的镜像点 $j = l+r-i$，则 $p_j$ 是之前已经求解过的。从而知道以 $j$ 为中心的最长子串长度为 $p_j$。但这一知识不能照搬到 $i$ 处，因为 $i+p_j$ 很可能会超过右端点 $r$。为此我们做一个截断，取 $p_i = min(p_j,r-i)$；
2. i 不在子串 t 内，即 $i > r$。此时我们取 $p_i=0$。

以上得到的 $p_i$ 其实还不是真正的解，因为 $i + p_i$ 的右侧还有未探明的情况。因此我们还需循环自增 $p_i$，直到 $s[i-p_i]\neq s[i+p_i]$。注意到随着 $p_i$ 的扩进，$s[i-p_i..i+p_i]$ 成为了新的端点最右的子串，因此我们还要及时更新 $t$。用 Python 实现的算法如下：

def manacher_odd(s):
    n = len(s)
    s = '^' + s + '$'
    p = [0] * n
    i = l = 1
    for i in range(1, n + 1):
        x = max(0, min(r - i, p[l + r - i]))
        while s[i + x] == s[i - x]: x += 1
    p[i - 1] = x - 1
    if i + x > r:
        l, r = i - x, i + x
    return p

为什么 Manacher 算法复杂度是 $O(n)$ 呢？我们可以从 $r$ 端点的变化考虑。在每次循环中，$r$ 有两种情形：

1. r 不变，此时 $p_i$ 是直接从其镜像点 $p_j$ 拿到的值，从而第二层的 while 循环没有运行；
2. r 增加，此时第二层的 while 循环执行了，将 $p_i$ 从 $r_\text{old}-i$ 增加到了 $r_\text{new} -i$。

由此可见，第二层 while 循环的总次数等于 $r$ 从始至终的增量，为 $n$。因此整个算法的时间复杂度为 $O(n)$。

同样地，我们还能计数 $s$ 中长度为偶数的回文子串。以下为 Python 代码，原理类似：

def manacher_even(s):
    # p[i] 记录了以字符 s[i] 后面的“槽”为中心的最长回文子串的长度的一半。
    # 如：
    # s = "aabbc"
    # p = [1, 0, 1, 0]
    n = len(s)
    s = '^' + s + '$'
    p = [0] * (n - 1)
    l = r = 1
    for i in range(1, n):
        j = max(0, min(r - i - 1, p[l + r - i - 3]))
        while s[i + j + 1] == s[i - j]:
            j += 1
        p[i - 1] = j
        if i + j + 2 > r:
            l, r = i - j + 1, i + j + 1
    return p

作者：hsfzxjy
链接：
许可：CC BY-NC-ND 4.0.
著作权归作者所有。本文不允许被用作商业用途，非商业转载请注明出处。