Manacher（马拉车）算法详解：求解最长回文子串

时间复杂度：O(n^2)

Manacher 算法

概念引入

1. 回文半径数组： d[i] (以 i 为中心的最长回文半径)。 例如，字符串 "#a#a#a#b#a#", 回文半径数组：

2. 两个重要的性质：

1. 回文串的长度为 d[i] - 1;
2. 以 i 为中心的回文串有 d[i] / 2 个。

3. 加速盒子（最右回文串）： 从前往后填表的过程中，区间 [l, r], 找到右端点最靠右的回文子串，不断维护区间。 它可以帮助我们加速填表。 如："#a#a#a#b#a#"； 依次维护的区间：[1, 1] -> [1, 3] -> [1, 5] -> [1, 7] -> [1, 7] -> [1, 7] -> [1, 7] -> [5, 11] -> [5, 11]

4. Manacher 算法 - 利用最右回文串加速更新回文半径数组

分类讨论（核心）

从前往后填表，当填到 d[i] 时，d[1] ~ d[i - 1] 均已经填好，并且维护最右回文串 [l, r]。当填写时，分下面大类，四种情况讨论：

1. i > r, 当前点没有在最右回文串中。此时，d[1] ~ d[i - 1] 的回文信息提供不了任何帮助。直接以 i 为中心暴力扩展（与中心扩展算法一致）；

2. i <= r, 当前点在最右回文串中，由对称性可知，j - l = r - i, 对称点 j = r - i + l 的回文半径 d[j], 分为以下三种情况进行讨论：

   • a. d[j] < r - i + 1（最长回文半径），即以 j 为中心的最长回文串包含在 [l, r] 内: 由对称性可知，d[i] = d[j] = d[r - i + l]
   • b. d[j] > r - i + 1，即以 j 为中心的最长回文串的左边界越过了 l: d[i] = r - i + 1。
   • c. d[j] = r - i = 1，即以 j 为中心的最长回文串的左边界正好在 l 位置： 此时 d[i] 至少为 d[j], 且还可能往外扩展。就可以从 d[j] 开始，用中心扩展算法暴力向外扩展。

注意这里： 1 和 2.c 情况还会涉及到对最右回文串区间 [l, r] 的更新。

时间复杂度：注意到，在整个算法执行的过程中 r 是不会回退的，相当于 i, r 两个指针不回退的向后移动。 因此整个时间复杂度为 O(n)。

代码实现： 这里非常的精妙，可以把 4 种情况都考虑进去。

string t, s;
int n, d[N];
// 预处理
void init() {
    cin >> t;
    s = ' ';
    for (auto ch : t) {
        s += '#';
        s += ch;
    }
    s += "##";
    n = s.size() - 2;
}

void get_d() {
    d[1] = 1;
    for (int i = 2, l = 1, r = 1; i <= n; i++) {
        int len = r >= i ? min(d[r - i + l], r - i + 1) : 1;
        // =1 是第 1 种情况，d[r - i + 1] 是第 2，r - i + 1 是第 3，两个相等，任取一个是第 4。
        while (s[i + len] == s[i - len]) len++;
        // 1，4 会进入循环，执行中心扩展算法，2，3 会判断不等
        if (i + len - 1 > r) r = i + len - 1, l = i - len + 1;
        // 更新区间
        d[i] = len;
    }
}

算法模板

题目：【模板】Manacher

代码：

#include <iostream>
using namespace std;
const int N = 2.2e7 + 10;
string t, s;
int m, n;
int d[N];

int main() {
    cin >> t;
    m = t.size();
    s += ' ';
    for (auto ch : t) {
        s += '#';
        s += ch;
    }
    s += "##";
    // 处理边界要不同
    n = s.size() - 2;
    d[1] = 1;
    int ret = 1;
    for (int i = 2, l = 1, r = 1; i <= n; i++) {
        int len = r >= i ? min(d[r - i + l], r - i + 1) : 1;
        while (s[i + len] == s[i - len]) len++;
        if (i + len - 1 > r) r = i + len - 1, l = i - len + 1;
        d[i] = len;
        ret = max(ret, d[i] - 1);
    }
    cout << ret << endl;
    return 0;
}