Manacher回文算法：求最长回文子串的线性时间算法
极难3什么是Manacher算法？它能帮你快速找到最长回文子串
同学们，你们有没有玩过一个文字游戏：正着读和反着读完全一样的句子，比如“上海自来水来自海上”？这样的字符串就叫回文串。在编程中，我们经常要从一个长字符串里找出最长的那个回文子串（连续的一段）。比如在“abbaabba”里，整个字符串本身就是回文，所以最长回文子串就是“abbaabba”。如果字符串是“abacdfgdcaba”，最长回文子串是“aba”或“aba”吗？其实还有更长的，比如“aba”？等等，这个例子不好，我们换个简单的：在“babad”中，最长回文子串是“bab”或“aba”。怎样又快又准地找到它呢？
最笨的方法——暴力枚举，需要挨个尝试所有可能的中心，向两边扩展比较，时间复杂度是O(n²)，当字符串很长时非常慢。而Manacher算法（中文常叫“马拉车算法”）可以在O(n)时间内完成，它的核心思想是：充分利用已经计算好的回文信息，像照镜子一样，根据左边的对称结果直接推断右边的情况，避免重复扩展。这个算法在字符串处理中非常经典，也是很多面试题的宠儿。
算法原理一步步拆解，像搭积木一样理解
1. 预处理：给字符串“加料”，让奇偶回文变得统一
原字符串里，回文长度可能是奇数（如“aba”），也可能是偶数（如“abba”）。如果直接处理，两种长度的中心点处理方式不同（奇数中心是一个字符，偶数中心是两个字符之间）。Manacher算法通过在每两个字符之间（包括首尾）插入一个不会在字符串中出现的分隔符（比如'#'），将所有回文都变成奇数长度。这样我们只需要处理“以每个位置为中心向两边扩展”这一种情况，简化问题。
例如：
- 原串 "aba" → 预处理后 "#a#b#a#"
- 原串 "abba" → 预处理后 "#a#b#b#a#"
注意新字符串的长度 = 2 * 原长 + 1，其中每个字符的位置都代表一个可能的回文中心（包括'#'，它代表偶数回文的中间位置）。
为什么分隔符可以统一奇偶？
原串中奇数回文"aba"以'b'为中心，预处理后中心还是'b'，但被#包围。原串中偶数回文"abba"的中心在第二个b和第三个b之间，预处理后恰好变成了以中间的'#'为中心。因此，所有原串中的回文，在预处理串中都有一个对应的中心位置，而且回文长度变成了奇数。
2. 回文半径 d[i]：这个中心到底能“撑”多远？
定义数组d[i]表示以预处理串中下标i为中心的最长回文半径长度（包括中心本身）。例如：
- 在 "#a#b#a#" 中，以'b'为中心（下标3），它向两边扩展到最远的回文串是"#a#b#a#"，从中心到最右边的距离是3（即下标3+3=6），所以
d[3] = 4（半径包含中心自己，实际到右端点的长度加1）。注意：回文串长度为2*d[i] - 1，但把它映射回原串时，去掉所有'#'，原串的回文长度就是d[i] - 1。
重要公式：
- 原串回文长度 =
d[i] - 1 - 原串回文的起始下标 =
(i - (d[i] - 1)) / 2（因为每个字符对应一个#，需要转换）
3. 对称性复用：用左边的“镜子”照出右边
Manacher算法维护两个变量：
- R：当前所有回文串中，最右边的右边界（即当前已知回文串能达到的最右下标+1，方便计算）。
- C：得到当前最右边界R的那个回文中心位置。
当我们从左到右计算d[i]时，如果i < R，说明位置i已经被包含在某个已经计算过的回文串内部，它的对称点j = 2*C - i正好在左边，并且我们已经知道d[j]。利用回文的对称性，d[i]至少可以取到min(d[j], R - i)。为什么取最小值？因为d[j]可能超出左边界的范围，而我们在右边最多只能扩展到R - i的位置（这里R - i表示从i到右边界的距离），超出部分还没有被验证，不能直接复制。
之后，再在这个“初始值”的基础上向两边继续扩展比较，直到不相等为止。这种利用对称信息的方法，大大减少了字符比较的次数，使得算法达到线性时间。
手绘示意图：以字符串"abba"为例
先预处理：原串"abba" → t = "#a#b#b#a#"
下标：0 1 2 3 4 5 6 7 8
字符：# a # b # b # a #
我们模拟计算d数组，用表格展示每一步：
| i | 字符 | 初始d[i] (由对称性) | 扩展后d[i] | 说明 |
|---|---|---|---|---|
| 0 | # | 1 | 1 | 最左边，只能自己 |
| 1 | a | 1 (i>=R? R=0, 所以d[1]=1) | 2 | 扩展一次：左右#和#相等，再扩越界，所以d[1]=2 |
| 2 | # | 1 | 1 | 中心间#，两边不匹配 |
| 3 | b | 1 | 1 | 左边a#b? 实际扩展遇到#和#? 注意：i=3时，左右字符t[2]=#, t[4]=#, 相等，d[3]变成2；再扩t[1]=a, t[5]=b, 不等，所以d[3]=2。过程略，实际上继续模拟... |
| ... | ... | ... | ... | 完整模拟建议手动在纸上画 |
关键点：当i=5时，R和C已经更新过（在i=3时，可能R=6? 我们一步步来）。
为了更清晰，我们可以写出一个简化版的模拟步骤：
初始：R=0, C=0
i=0: d[0]=1, 扩展后还是1; i+d[i]=1 > R=0, 更新R=1, C=0
i=1: i<R? 1<1? 不成立，所以d[1]=1; 扩展：t[0]==t[2]? '#'=='#' 成立，d[1]=2; 再扩t[-1]越界，停止。i+d[i]=3 > R=1, 更新R=3, C=1
i=2: i<R? 2<3成立，j=21-2=0, d[0]=1, R-i=1, min=1, d[2]=1; 扩展：t[1]==t[3]? 'a'=='b'? 不等，保持d[2]=1; i+d[i]=3, R=3, 不更新
i=3: i<R?3<3不成立，d[3]=1; 扩展：t[2]==t[4]? '#'=='#' →d[3]=2; t[1]==t[5]? 'a'=='b'? 不等，停止；i+d[i]=5 > R=3, 更新R=5, C=3
i=4: i<R?4<5成立，j=23-4=2, d[2]=1, R-i=1, min=1, d[4]=1; 扩展：t[3]==t[5]? 'b'=='b'? 相等，d[4]=2; t[2]==t[6]? '#'=='#'? 相等，d[4]=3; t[1]==t[7]? 'a'=='a'? 相等，d[4]=4; t[0]==t[8]? '#'=='#'? 相等，d[4]=5; 再扩越界。i+d[i]=9 > R=5, 更新R=9, C=4
i=5: i<R?5<9成立，j=24-5=3, d[3]=2, R-i=4, min=2, d[5]=2; 扩展：t[3]==t[7]? 'b'=='a'? 不等，停止；i+d[i]=7 < R, 不更新
i=6: i<R?6<9成立，j=24-6=2, d[2]=1, R-i=3, min=1, d[6]=1; 扩展：t[5]==t[7]? 'b'=='a'? 不等，停止
i=7: i<R?7<9成立，j=24-7=1, d[1]=2, R-i=2, min=2, d[7]=2; 扩展：t[6]==t[8]? '#'=='#'? 相等，d[7]=3; 再扩越界；i+d[i]=10 > R=9, 更新R=10? 实际下标最大8，d[7]=3, i+d[i]=10超界，但R只记录到8+1? 注意条件：i+d[i] > R，这里i+d[i]=10,R=9，所以更新R=10,C=7
i=8: i<R?8<10成立，j=27-8=6, d[6]=1, R-i=2, min=1, d[8]=1; 扩展：t[7]==t[9]? 越界，停止。
最终d数组： [1,2,1,2,5,2,1,3,1]
原串最长回文长度 = max(d[i]-1) = 5-1=4，对应中心i=4（即原串中间的'#'），原串起始下标 = (4-4)/2=0，长度4，所以结果是"abba"（原串从0开始取4个字符）。正确！
算法完整步骤回顾
- 预处理：在原串每个字符之间和首尾插入分隔符'#'，得到新串t。
- 初始化：定义数组d大小n（n=t长度），初始值都可以设为1（因为至少包含自己）。定义R=0, C=0。
- 遍历每个位置i（0到n-1）：
- 如果i < R，则
d[i] = min(d[2*C - i], R - i)；否则d[i]=1。 - 然后通过while循环尝试向两边扩展：只要
t[i - d[i]] == t[i + d[i]]，就把d[i]加1。 - 如果
i + d[i] > R，则更新R = i + d[i]，C = i。
- 如果i < R，则
- 找最长：在遍历过程中记录最大的
d[i] - 1以及对应的中心位置i。 - 还原：根据最长回文的中心i和半径d[i]，计算它在原串中的起始位置
(i - (d[i]-1)) / 2，然后用原串的substr取出。
常见新手错误（避开这些坑）
- 忘记处理边界：在while扩展时，一定要判断
i - d[i] >= 0和i + d[i] < n，否则会越界导致运行时错误。 - 对称点计算错误：
j = 2 * C - i要确保C和i是预处理串中的下标。有些同学直接用了原串下标，导致计算出的对称点不对。 - 误解
d[i]的含义：d[i]是包括中心自己的半径长度，而不是回文长度。回文在原串的长度是d[i]-1。 - 更新R和C的时机：当
i + d[i] > R时才更新，注意是大于，而不是大于等于。如果等于，其实不需要更新，因为旧中心还能覆盖同样范围。 - 将镜像对称与中心对称混淆：
d[2*C - i]是镜像点的半径，但可能超出左边界，需要用R - i限制，取最小值。 - 错误地认为所有回文都能从左边完全复制：事实上，只能复制不超过
R - i的部分，超出部分必须自己扩展。
完整可运行代码（C++和Python），每行都有中文注释
C++代码
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
string manacher(const string &s) {
// 预处理：每两个字符之间加一个'#'
string t = "#";
for (char c : s) {
t += c; // 添一个原串字符
t += '#'; // 再添分隔符
}
int n = t.size(); // 预处理串长度
vector<int> d(n, 1); // d[i]表示以i为中心的回文半径，至少为1
int R = 0, C = 0; // 当前最右回文边界的下一个位置，及对应的中心
int maxCenter = 0, maxLen = 0; // 记录最长回文的中心下标和长度
for (int i = 0; i < n; i++) {
// 利用对称性初始化d[i]
if (i < R) {
// j = 2*C - i 是i关于C的对称点
int j = 2 * C - i;
d[i] = min(d[j], R - i); // 不能超过R - i
}
// 中心扩展：尝试向两边扩展
while (i - d[i] >= 0 && i + d[i] < n && t[i - d[i]] == t[i + d[i]]) {
d[i]++; // 能扩展，半径加1
}
// 如果能延伸得更远，更新最右边界和中心
if (i + d[i] > R) {
R = i + d[i]; // 新的右边界（注意这是开区间，即返回的下标+1）
C = i; // 新的中心
}
// 检查当前回文长度是否更大
if (d[i] - 1 > maxLen) {
maxLen = d[i] - 1; // 原串回文长度 = d[i] - 1
maxCenter = i; // 记录中心
}
}
// 从预处理串还原原串子串
// 原串起始下标： (maxCenter - maxLen) / 2
int start = (maxCenter - maxLen) / 2;
return s.substr(start, maxLen);
}
int main() {
string s1 = "abbaabba";
cout << "在\"" << s1 << "\"中最长回文子串: " << manacher(s1) << endl;
string s2 = "ababa";
cout << "在\"" << s2 << "\"中最长回文子串: " << manacher(s2) << endl;
string s3 = "babad";
cout << "在\"" << s3 << "\"中最长回文子串: " << manacher(s3) << endl;
return 0;
}
Python代码
def manacher(s):
"""
返回字符串s中的最长回文子串
"""
# 预处理：每两个字符之间加'#'
t = '#' + '#'.join(s) + '#'
n = len(t) # 预处理串长度
d = [1] * n # 每个位置的回文半径，初始为1
R, C = 0, 0 # 最右右边界（开区间），对应中心
max_center, max_len = 0, 0 # 记录最长回文的中心和长度
for i in range(n):
# 利用对称性快速初始化
if i < R:
j = 2 * C - i # 对称点下标
d[i] = min(d[j], R - i) # 不能超过右边界
# 中心扩展
while i - d[i] >= 0 and i + d[i] < n and t[i - d[i]] == t[i + d[i]]:
d[i] += 1 # 扩展成功，半径加1
# 更新最右边界
if i + d[i] > R:
R = i + d[i] # 更新右边界
C = i # 更新中心
# 记录最长回文
if d[i] - 1 > max_len:
max_len = d[i] - 1 # 原串回文长度 = d[i] - 1
max_center = i
# 还原原串中的子串
start = (max_center - max_len) // 2 # 原串起始下标
return s[start: start + max_len]
# 测试
print(manacher("abbaabba")) # 输出: abbaabba
print(manacher("ababa")) # 输出: ababa
print(manacher("babad")) # 输出: bab 或 aba（取决于实现，这里返回bab）
运行上面代码，你能看到每个字符串的最长回文子串被正确找出。
总结与延伸
Manacher算法的精妙之处在于利用对称性复用已计算信息，从而将时间复杂度从O(n²)降到O(n)。它需要你理解：
- 预处理统一奇偶回文
- 回文半径的定义和与原串长度的关系
- 镜像对称点的计算和min限制
- 维护最右边界R和中心C
掌握了这个算法，你还能解决类似的问题，比如“回文子串计数”（统计一个字符串中所有回文子串的个数）——只需在遍历过程中累加d[i]/2即可（因为每个中心贡献了 floor(d[i]/2) 个原串回文子串）。
如果你想了解更多字符串算法，可以继续学习：
- KMP算法：用于字符串匹配，也是线性时间。
- Z算法：计算每个后缀与原串的最长公共前缀，与Manacher有相似之处。
- 后缀数组 / 后缀自动机：更高级的字符串处理工具。
Manacher算法虽然代码短小，但理解背后的对称思想需要多动手模拟。建议你用一张纸、一支笔，自己给几个小例子（比如“aaab”、“aabaa”）模拟d数组的计算过程，慢慢就会豁然开朗。加油！
例题精讲
在Manacher算法中，数组p[i]通常表示什么？
Manacher算法能够在O(n)时间内找到所有回文子串的关键原因是什么？
Manacher算法在预处理时，在字符串每两个字符之间以及首尾插入相同的分隔符（如'#'），使得原字符串长度变为2n+1，从而统一处理奇偶回文。经过这种变换后，原字符串中的最长回文子串在变换后的字符串中一定对应一个以'#'为中心的奇数长度回文吗？
以下代码是Manacher算法求最长回文子串长度的C++实现，请补全while循环的条件（填空1）和更新mx与id的语句（填空2）。
int manacher(string s) {
string t = "$#";
for (char c : s) {
t += c;
t += '#';
}
vector<int> p(t.size(), 0);
int mx = 0, id = 0, resLen = 0;
for (int i = 1; i < t.size(); i++) {
p[i] = mx > i ? min(p[2*id-i], mx-i) : 1;
while (___①___) {
p[i]++;
}
if (___②___) {
mx = i + p[i];
id = i;
}
resLen = max(resLen, p[i]);
}
return resLen - 1;
}以下代码是Manacher算法求最长回文子串具体内容的C++实现片段，请补全计算原串中起始位置的表达式（填空）。
int manacher(string s) {
string t = "$#";
for (char c : s) {
t += c;
t += '#';
}
vector<int> p(t.size(), 0);
int mx = 0, id = 0, center = 0, maxLen = 0;
for (int i = 1; i < t.size(); i++) {
p[i] = mx > i ? min(p[2*id-i], mx-i) : 1;
while (i + p[i] < t.size() && i - p[i] >= 0 && t[i + p[i]] == t[i - p[i]]) p[i]++;
if (i + p[i] > mx) {
mx = i + p[i];
id = i;
}
if (p[i] > maxLen) {
maxLen = p[i];
center = i;
}
}
int start = ___; // 在原串s中的起始下标
return s.substr(start, maxLen - 1);
}