Manacher 算法详解：线性时间求解最长回文子串
在字符串处理问题中，寻找最长回文子串是一个经典场景。虽然中心扩展法直观易懂，但其时间复杂度为 O(n²)，在处理大规模数据时显得力不从心。Manacher（马拉车）算法通过巧妙的预处理和对称性优化，将时间复杂度降低至 O(n)，是解决此类问题的利器。
核心问题定义
我们需要解决两个关联问题：
- 找出字符串中所有的回文子串。
- 找出其中长度最长的一个。
这两个目标可以通过同一套逻辑同时达成。
基础概念与预处理
什么是回文？
正读和反读都一样的字符串称为回文串。根据长度奇偶性，可分为奇回文串（如 "aba"）和偶回文串（如 "abba"）。为了统一处理，我们引入以下概念：
- 回文中心：回文串最中间的位置。
- 回文半径：从中心到回文串端点的距离（包含中心本身）。
预处理：统一奇偶性
中心扩展法需要分别处理奇数和偶数长度的情况，这增加了代码复杂度。Manacher 算法的核心技巧之一是在字符之间插入特殊分隔符（通常用 #），将所有回文串转化为奇数长度。
例如，原串 abcbaa 经过处理后变为 #a#b#c#b#a#a#。
- 原奇回文
bab->#b#a#b# - 原偶回文
abba->#a#b#b#a#
这样处理后，所有回文串的中心都落在某个字符上，无需区分奇偶，只需枚举所有中心点即可。
中心扩展法回顾
在理解 Manacher 之前，先回顾一下基础的暴力解法：以每个位置为中心向两边扩展。
string t, s;
int n;
// 预处理函数
void init(const string& str) {
s = "#";
for (char ch : str) {
s += ch;
s += '#';
}
n = s.size();
}
// 中心扩展求最长半径
int expand(int center) {
int d = 1;
while (center - d >= 0 && center + d < n && s[center - d] == s[center + d]) {
d++;
}
return d - 1; // 实际回文长度相关值
}
该算法的时间复杂度为 O(n²)。当字符串较长时，性能瓶颈明显。
Manacher 算法核心原理
Manacher 算法的关键在于利用已计算的信息加速后续计算。我们维护一个数组 d[i]，表示以 i 为中心的最长回文半径。同时，维护一个当前遍历到的最右回文边界 [l, r]。
关键性质
- 回文半径数组：
d[i]记录以i为中心的回文半径。 - 对称性：如果当前位置
i在最右边界r之内，那么它关于中心l + r - i的对称点j的回文信息可以复用。 - 边界更新：只有当新回文串的右端点超过
r时，才更新l和r。
分类讨论
当我们计算 d[i] 时，分两种主要情况：
- i > r：当前点在已知最右回文串之外。此时没有历史信息可用，只能像中心扩展法一样暴力向外扩展，并更新
l和r。 - i <= r：当前点在已知范围内。利用对称点
j = l + r - i的信息：- 若
d[j] < r - i + 1：说明j的回文串完全在[l, r]内，由对称性可知d[i] = d[j]。 - 若
d[j] > r - i + 1：说明j的回文串超出了左边界l，则i的回文串至少延伸到r，即d[i] = r - i + 1，之后需继续尝试扩展。 - 若
d[j] == r - i + 1：边界刚好触及，同样需要尝试继续扩展。
- 若
这种策略保证了 r 指针在整个过程中只增不减，从而实现了 O(n) 的时间复杂度。
完整代码实现
下面是一个标准的 C++ 实现模板，可直接用于求解最长回文子串长度。
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 2200005; // 根据题目规模调整
string t, s;
int d[N];
// 预处理：添加分隔符
void init() {
cin >> t;
s = "#";
for (char ch : t) {
s += ch;
s += '#';
}
}
// Manacher 算法主逻辑
int manacher() {
int n = s.size();
int max_len = 0;
int l = 0, r = -1; // 当前最右回文边界 [l, r]
for (int i = 0; i < n; i++) {
int k = (i > r) ? 1 : min(d[l + r - i], r - i + 1);
// 尝试扩展
while (i - k >= 0 && i + k < n && s[i - k] == s[i + k]) {
k++;
}
d[i] = k;
// 更新最右边界
if (i + k - 1 > r) {
l = i - k + 1;
r = i + k - 1;
}
// 记录最大回文半径
max_len = max(max_len, k - 1);
}
return max_len;
}
int main() {
init();
cout << manacher() << endl;
return 0;
}
总结
Manacher 算法通过预处理消除奇偶差异，并利用回文串的对称性避免了大量重复比较。在实际工程中，如果你需要频繁查询或处理超长字符串的回文特征，这个算法是首选方案。记住，维护好 l 和 r 边界是理解该算法的关键所在。
对于更复杂的变体问题（如查找所有回文子串数量等），可以在上述基础上稍作修改。建议配合洛谷 P3805 等经典题目进行实战练习，加深理解。