Manacher 算法

马拉车算法。

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

例如 "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;
}

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