在字符串处理中，最长回文子串是一个经典问题。给定一个字符串，我们需要找出其中最长的、正读和反读都一样的连续子串。朴素做法是以每个字符或每两个相邻字符为中心向两边扩展，最坏情况下时间复杂度为O(n^2)。Manacher算法由Glenn Manacher提出，能够在O(n)时间内解决该问题，其核心思想是利用已经计算出的回文信息来减少重复匹配。
一、Manacher算法基本原理
Manacher算法首先对待处理字符串进行预处理：在原串的每两个字符之间以及首尾各插入一个不会在原串中出现的分隔符（通常用井号#），这样无论原回文子串长度是奇数还是偶数，在新串中都变成了以某个字符为中心、长度为奇数的回文。例如原串为"abba"，处理后变为"#a#b#b#a#"，最长回文中心落在中间两个b之间的#上。
算法维护两个关键变量：最右回文边界right表示当前所有已计算回文中向右延伸最远的位置，以及该回文对应的中心center。同时用一个数组p，其中p[i]记录以新串第i个字符为中心的最长回文半径（包含中心，半径长度即向右或向左能匹配到的字符数）。利用镜像对称，当i小于right时，可以先取i关于center的对称位置mirror = 2*center - i的p值，再与right - i取较小值作为p[i]的初始值，从而跳过不必要的比较。
1.1 预处理函数
下面给出预处理的C++实现。我们在原串s的每个字符前后加#，并在最前面加一个^、最后面加$以避免边界判断，这些字符均不与#和原字符冲突。
#include <string>
using namespace std;
// 预处理：将字符串转换为统一奇数长度形式
string preProcess(const string& s) {
if (s.empty()) return "^$";
string t = "^";
for (char c : s) {
t += "#";
t += c;
}
t += "#$";
return t;
}
上述代码中，^和$仅作为哨兵，防止数组越界。实际匹配时不会用到它们参与回文判定，因为遇到这两个字符必然不匹配。预处理后的串长度变为2*n+3，空间开销很小。
二、核心算法实现
在预处理基础上，我们用循环遍历新串t的每个位置i，动态更新center和right，并填充数组p。每次先按镜像规则赋初值，再从初值向外尝试扩展，最后根据p[i]和i更新最右边界。最终最长回文半径减一即为原串中的最长回文长度。
2.1 完整C++代码
#include <iostream>
#include <string>
#include <vector>
using namespace std;
string longestPalindrome(const string& s) {
string t = preProcess(s);
int n = t.size();
vector<int> p(n, 0);
int center = 0, right = 0;
for (int i = 1; i < n - 1; i++) {
int mirror = 2 * center - i;
if (right > i) {
p[i] = min(right - i, p[mirror]);
} else {
p[i] = 0;
}
// 尝试扩展
while (t[i + 1 + p[i]] == t[i - 1 - p[i]]) {
p[i]++;
}
// 更新最右边界和中心
if (i + p[i] > right) {
center = i;
right = i + p[i];
}
}
// 寻找最大半径
int maxLen = 0, idx = 0;
for (int i = 1; i < n - 1; i++) {
if (p[i] > maxLen) {
maxLen = p[i];
idx = i;
}
}
// 原串中的起始位置
int start = (idx - maxLen) / 2;
return s.substr(start, maxLen);
}
string preProcess(const string& s) {
if (s.empty()) return "^$";
string t = "^";
for (char c : s) {
t += "#";
t += c;
}
t += "#$";
return t;
}
int main() {
string s = "ababababa";
cout << longestPalindrome(s) << endl;
return 0;
}
这段代码中，preProcess函数已在前面说明。主逻辑里，right > i时利用镜像初始化p[i]，否则从0开始。扩展循环条件t[i + 1 + p[i]] == t[i - 1 - p[i]]依靠哨兵^和$保证不越界。最终maxLen就是原串最长回文长度，idx为中心，通过(start = (idx - maxLen) / 2)映射回原串下标。
2.2 复杂度分析
虽然代码中有两层看似嵌套的循环，但内层while扩展的总次数不会超过right向右滑动的总距离，即最多推进n次，因此整体时间复杂度为O(n)。空间上需要长度为O(n)的p数组和预处理串，也是线性开销。相比中心扩展法的O(n^2)，在长字符串场景下优势明显。
需要注意，当输入字符串极长且包含大量重复字符时，Manacher依然稳定线性，而某些基于动态规划的方法会因O(n^2)空间或时间被淘汰。这也是算法竞赛中偏好Manacher的原因。
三、常见误区与调试建议
初学者容易直接在原始串上分奇偶讨论，导致代码分支繁多且容易漏掉边界。统一插入分隔符是简化逻辑的关键一步。另外，有些人会错误地把right初始化为0后忘记在扩展后更新center，造成镜像位置计算错误，进而退化成暴力。
调试时建议打印预处理串t和p数组，观察每个中心的半径是否符合直观。例如对"aba"，t为"^#a#b#a#$"，p数组在b对应位置应为3，表示半径3即原长3。若发现p值偏小，通常是因为扩展条件写反或哨兵字符参与比较。
3.1 与中心扩展法对比
| 方法 | 时间复杂度 | 代码复杂度 | 适用场景 |
|---|---|---|---|
| 中心扩展 | O(n^2) | 低 | 短串、教学演示 |
| Manacher | O(n) | 中 | 长串、竞赛、面试 |
从上表可以看出，Manacher以稍高的实现难度换取了线性的性能保障。在实际工程中若字符串长度不确定且可能很大，应优先采用该算法。
四、总结
通过预处理统一奇偶回文、借助回文半径数组与最右边界的镜像复用，Manacher算法把最长回文子串问题优化到了线性时间。本文给出的C++实现包含完整预处理、核心循环与结果提取，并分析了复杂度与易错点。读者可在本地编译器运行示例，修改输入串观察输出，从而彻底理解每个变量的作用。
掌握了这一算法后，类似的问题如回文子串计数、最长回文前缀等都能基于相同思想快速变形解决，是字符串处理工具箱中实用的一环。
Manacher算法C++字符串处理最长回文子串修改时间：2026-08-06 07:57:34