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

例如 $\mathtt{\text{banana}}$ 的最长回文子串是 $\mathtt{\text{anana}}$。

预处理

「奇数长度」和「偶数长度」的回文子串其实有区别。例如 $\mathtt{\text{aba}}$ 的中心是一个字符，但 $\mathtt{\text{abba}}$ 的中心位于两个字符之间。

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

那么，针对「奇数长度」的回文子串，要以「字符」为中心扩展；针对「偶数长度」的回文子串，要以「字符间隙」为中心扩展。这意味着算法需要分别处理这两种情况，非常的麻烦。

并且，当回文子串扩展到字符串的开头和结尾时，需要额外的边界检查来防止数组越界。

Manacher 通过预处理来规避这些麻烦。

优化 1

Manacher 在字符间隙（包括字符串首尾）各插入一个特殊字符（如 $\mathtt{\text{\#}}$），这么一来，就只需考虑长度为奇数的情况。

• $\mathtt{\text{aba}}\to \mathtt{\text{\#a\#b\#a\#}}$
• $\mathtt{\text{abba}}\to \mathtt{\text{\#a\#b\#b\#a\#}}$

优化 2

Manacher 在字符串的开头和结尾添加 不同 的特殊字符，这样一旦扩展到边界就会自动停止。

• $\mathtt{\text{aba}}\to \mathtt{\text{@\#a\#b\#a\#\%}}$
• $\mathtt{\text{abba}}\to \mathtt{\text{@\#a\#b\#b\#a\#\%}}$

WARNING

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

原理

以下是一些变量的定义：

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

  例如对 $\mathtt{\text{abacab}}$，以第 $3$ 个字符 $\mathtt{\text{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$；
• 否则令 $p[i]=min\{p[2M-i],R-i\}$。

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

最后遍历数组 $p$，$p$ 中的最大值即为最长回文子串的半径。

WARNING

最后务必要把特殊字符去除掉。

---

每次暴力扩展的起点都是 $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. 回文串是指正读和反读都相同的字符串。 ↩︎