Manacher 算法

很多人喜欢叫它马拉车算法。

Manacher 算法可以在 $O(n)$ 的时间复杂度下找到字符串的最长回文子串1。

例如 "banana" 的最长回文子串是 "anana"。

预处理 #

「奇数长度的回文子串」和「偶数长度的回文子串」其实是有所区别的。例如 "aba" 的中心是一个字符,但 "abba" 的中心位于两个字符之间。

在探测回文子串的长度时,我们所采用的是「中心扩展法」,即确定中心并向两侧逐步扩展,直到两端的字符不同为止。

那么针对奇数长度的回文子串,要以字符为中心扩展;针对偶数长度的回文子串,要以字符间隙为中心扩展。这意味着算法需要分别处理这两种情况,想想就头大。

Manacher 采用了一个很聪明的方法:在字符间隙(包括字符串首尾)各插入一个特殊字符(比如 #),这么一来,就只需要考虑长度为奇数的情况。

"aba" → "#a#b#a#"

"abba" → "#a#b#b#a#"

另一个预处理优化是,当回文子串扩展到字符串的开头和结尾时,需要额外的边界检查来防止数组越界,也比较麻烦。我们可以再在字符串的开头和结尾添加不同的特殊字符,这样一旦扩展到边界就会自动停止。

"aba" → "^#a#b#a#$"

"abba" → "^#a#b#b#a#$"

注:不得使用原字符串中存在的字符作为特殊字符。

算法主体 #

以下是一些变量的定义:

  • 创建数组 $p$,其中 $p[i]$ 表示以第 $i$ 个字符为中心,能扩展的最大次数。

    例如对 "abacab",以第 $3$ 个字符 c 为中心,最多可以向左右扩展 $2$ 次,就记 $p[3]=2$。

  • 使用两个变量 $M$ 和 $R$ 描述当前已知的最靠右的回文串的信息。

    • $M$ 是其中心位置,初始为 $0$;
    • $R$ 是其右边界位置,初始为 $0$。

Manacher 算法的主要策略是:从左至右依次计算 $p[i]$,并实时地更新 $M$ 和 $R$ 的值。

假设当前要计算 $p[i]$,则此时应已经算出了 $p[1],p[2],\cdots,p[i-1]$ 以及当前的 $M$ 和 $R$。

  • Case 1: $i$ 在 $R$ 之内:

    可以找到 $i$ 关于 $M$ 的对称点 $2M-i$。

    由于蓝色区域是一个回文串,这意味着我们可以通过其对称性获取到一些信息。

    • Case 1.1: 若 $p[2M-i]\le R-i$:

      我们知道 $R-i$ 也是 $2M-i$ 到蓝区左端的距离。这种情况实际上是在说:以 $2M-i$ 为中心扩展,扩不出蓝区的范围。

      由蓝区的对称性可知,以 $i$ 为中心的「可扩展程度」和以 $2M-i$ 为中心的「可扩展程度」是相同的,于是有 $p[i]=p[2M-i]$。

    • Case 1.2: 若 $p[2M-i]>R-i$:

      以 $2M-i$ 为中心扩展,可以扩展到蓝区外面。

      由于蓝区以外的情况我们并不知晓,这种情况下 $p[i]$ 只能有一个 $R-i$ 的保底。我们直接从 $R$ 开始继续暴力扩展,从而得到 $p[i]$ 的实际值。

      扩展完成后,我们得到了一个更靠右的回文串,需要相应地更新 $M$ 和 $R$ 的值。

  • Case 2: $i$ 在 $R$ 之外:

    这种情况就只能直接暴力扩展了。扩展完成后同样要更新 $M$ 和 $R$。

进一步简化算法的过程:

  • 若 $i> R$,则令 $p[i]=0$;

  • 否则令 $\DeclareMathOperator{\min}{min} p[i]=\min(p[2M-i],R-i)$。

在此基础上,继续暴力扩展,得到 $p[i]$ 的实际值,并更新 $M$ 和 $R$。

最后遍历数组 $p$,$p$ 中的最大值即为最长回文子串的半径。最后要记得把特殊字符去除掉。


每次暴力扩展的起点都是 $R$,扩展完成后 $R$ 又更新了过去,作为下一次暴力扩展的起点。在扩展的过程中,每个字符都只被访问了一次。故时间复杂度为 $O(n)$。

模板 #

#include <bits/stdc++.h>

using namespace std;

string manacher(const string &s) {
    string t = "^#";
    for (char c : s) {
        t += c;
        t += "#";
    }
    t += '$';

    vector<int> p(t.size());
    int M = 0, R = 0;
    for (int i = 1; i < t.size() - 1; i ++) {
        p[i] = (i > R) ? 0 : min(p[2 * M - i], R - i);
        while (t[i + p[i] + 1] == t[i - p[i] - 1])
            p[i] ++;
        if (i + p[i] > R) {
            M = i;
            R = i + p[i];
        }
    }

    int maxM = 0, maxP = 0;
    for (int i = 1; i < t.size() - 1; i ++) {
        if (p[i] > maxP) {
            maxM = i;
            maxP = p[i];
        }
    }

    int start = (maxM - maxP) / 2;
    return s.substr(start, maxP);
}

int main() {
    string s;
    cin >> s;
    cout << manacher(s) << endl;
    return 0;
}

  1. 回文串是指正读和反读都相同的字符串。 ↩︎