Manacher 算法详解：求解最长回文子串

Manacher（马拉车）算法

问题

1. 在字符串中，找出所有的回文子串；
2. 在字符串中，找出最长的回文子串。

两个问题可以结合解决。

1. 相关概念引入

1. 回文字符串： 正着读和反着读都一样的字符串就是回文字符串。

2. 回文子串： 一个字符串的某个字串是回文。

3. 奇回文串： 回文串的字符数为奇数。

4. 偶回文串： 回文串的字符数为偶数。

5. 回文中心： c，回文串最中心的位置。奇回文串（回文中心）：n + 1 / 2; 偶回文串（回文中心）：n / 2 与 n/2 + 1 之间。

6. 回文半径： d，回文中心到回文半径左/右端点的距离（字符数，包括本身）。

2. 中心扩展算法

算法原理

1. 从前往后遍历字符串，以 s[i] 或 s[i] 与 s[i + 1] 的中间作为回文串的中心位置；
2. 从中间位置开始，枚举半径长度，逐渐向两边扩展，找出以该点为中心的最长的回文子串。

预处理

为了防止对奇偶回文字串进行分类讨论，且奇回文字串更好处理，这里将其统一转化为奇回文串。

预处理字符串： 在相邻字符之间和整个字符串的两端任意加入一个字符 '#'。

例如，字符串 s = "abcbaa" 经过预处理之后就变成：s = "#a#b#c#b#a#a#"。

经过预处理之后： 本来是奇回文串，处理之后依旧是奇回文串。例如 "bab" 处理后为 "#b#a#b#"； 本来是偶回文串，处理之后就变成奇回文串。例如 "abba" 处理后为 "#a#b#b#a#"； 此时，在处理之后的串上跑中心扩展算法时，由于所有的回文串都是奇回文串，仅需枚举所有中心点，即可找到所有的回文串。

注意： （不用像 kmp 算法那样，加入一个不会出现的字符，这里可以加入任意字符。因为判断回文的时候，只会原始字符和原始字符判断，新加入的字符和新加入的字符判断。因此，可以加入任意字符。）

代码：

string t, s;
int m, n;
// 以求解最长回文子串为例
int fun() {
    // 预处理字符串
    cin >> t;
    m = t.size();
    s += ' '; // 这里要处理边界不同，' ' != '#'
    for (auto ch : t) {
        s += '#';
        s += ch;
    }
    s += "##";
    n = s.size() - 2;
    int ret = 1;
    // 中心扩展算法
    for (int i = 1; i <= n; i++) {
        int d = 1; // 枚举向右向左的距离
        while (s[i - d] == s[i + d]) d++;
        ret = max(ret, d - 1);
    }
    return ret;
}

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

3. Manacher 算法

概念引入

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

字符串	#	a	#	a	#	a	#	b	#	a	#
下标	1	2	3	4	5	6	7	8	9	10	11
回文半径	1	2	3	4	3	2	1	4	1	2	1

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;
    }
}

4. 算法模板

代码：

#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;
}