Manacher 算法是解决最长回文子串问题的线性时间算法。通过预处理字符串消除奇偶回文差异，利用回文对称性记录已遍历区域信息，将时间复杂度从 O(n^2) 降至 O(n)。文章涵盖核心原理、C++ 完整实现、进阶优化及实战应用，对比了中心扩展法与回文自动机，提供了常见错误分析与注意事项。
Manacher 算法（马拉车算法）是专门解决最长回文子串问题的线性时间算法，由 Glenn Manacher 在 1975 年提出。它通过对字符串进行预处理（插入特殊字符）消除奇偶回文的差异，并利用'回文对称性'记录已遍历区域的信息，避免重复计算，将时间复杂度从中心扩展法的 O(n^2) 降至 O(n)。本文将从核心原理、预处理、算法流程到实战优化，全面解析 Manacher 算法的设计思想与 C++ 实现技巧。
最长回文子串的经典解法是中心扩展法：遍历每个字符（奇数长度回文的中心）和每两个字符之间的间隙（偶数长度回文的中心），向两边扩展直到字符不匹配。
// 中心扩展法示例（O(n^2)）
int expand(const string& s, int l, int r) {
while (l >= 0 && r < s.size() && s[l] == s[r]) {
l--; r++;
}
return r - l - 1; // 回文长度
}
string longestPalindrome_brute(const string& s) {
if (s.empty()) return "";
int start = 0, max_len = 0;
for (int i = 0; i < s.size(); ++i) {
int len1 = expand(s, i, i); // 奇数长度
int len2 = expand(s, i, i+1); // 偶数长度
int len = max(len1, len2);
if (len > max_len) {
max_len = len;
start = i - (len - 1) / 2;
}
}
return s.substr(start, max_len);
}
缺陷：对每个中心都要重复扩展，最坏情况下（如全为相同字符的字符串）时间复杂度为 O(n^2)，数据量大时效率极低。
Manacher 算法通过两个关键优化实现线性时间：
#），将奇偶长度的回文统一为奇数长度（如 abba → #a#b#b#a#），避免分别处理奇偶情况；center 和右边界 right，对于当前位置 i，若 i 在 right 内，可通过对称位置 mirror = 2*center - i 的回文长度，直接得到 i 的初始回文长度，避免重复扩展。给定预处理后的字符串 t（如 s=abba → t=#a#b#b#a#），定义：
p[i] 表示以 t[i] 为中心的最长回文子串的半径（即从中心到右边界的字符数，包含中心）；
t=#a#b#b#a#，p[4]=4（中心为 t[4]，回文半径 4，对应原字符串的 abba，长度为 p[i]-1）；p[i] → 原字符串回文长度 = p[i] - 1；i → 原字符串起始位置 = (i - p[i]) / 2。示例：s=abba → t=#a#b#b#a#，p 数组为 [0,1,0,1,4,1,0,1,0]：
p[4]=4 → 原回文长度 = 4-1=4（对应 abba）；插入特殊字符 #，并在首尾添加不同的边界字符（如 ^ 和 $），避免越界判断：
// 预处理字符串：s → ^#s[0]#s[1]#...#s[n-1]#$
string preprocess(const string& s) {
int n = s.size();
if (n == 0) return "^$";
string res = "^"; // 左边界
for (int i = 0; i < n; ++i) {
res += "#" + s.substr(i, 1);
}
res += "#$"; // 右边界
return res;
}
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
// Manacher 算法：返回最长回文子串
string manacher(const string& s) {
string t = preprocess(s);
int n = t.size();
vector<int> p(n, 0); // p 数组：存储回文半径
int center = 0, right = 0; // 当前最右回文的中心和右边界
// 遍历预处理后的字符串（跳过边界^和$）
for (int i = 1; i < n - 1; ++i) {
// 步骤 1：计算对称位置
int mirror = 2 * center - i; // i 关于 center 的对称位置
// 步骤 2：初始化 p[i]（利用对称性）
if (i < right) {
p[i] = min(right - i, p[mirror]);
}
// 步骤 3：中心扩展（核心）
while (t[i + p[i] + 1] == t[i - (p[i] + 1)]) {
p[i]++;
}
// 步骤 4：更新 center 和 right（如果当前回文右边界超过 right）
if (i + p[i] > right) {
center = i;
right = i + p[i];
}
}
// 步骤 5：找到 p 数组中的最大值（最长回文半径）
int max_len = 0, center_idx = 0;
for (int i = 1; i < n - 1; ++i) {
if (p[i] > max_len) {
max_len = p[i];
center_idx = i;
}
}
// 步骤 6：转换为原字符串的起始位置和长度
int start = (center_idx - max_len) / 2;
return s.substr(start, max_len);
}
// 测试代码
int main() {
vector<string> test_cases = {"abba", "cbbd", "a", "ac", "ccc", "abcba"};
for (const string& s : test_cases) {
string res = manacher(s);
cout << "原字符串：" << s << " → 最长回文子串：" << res << endl;
}
return 0;
}
输出结果：
原字符串：abba → 最长回文子串：abba
原字符串：cbbd → 最长回文子串：bb
原字符串：a → 最长回文子串：a
原字符串：ac → 最长回文子串：a
原字符串：ccc → 最长回文子串：ccc
原字符串：abcba → 最长回文子串：abcba
# 后，所有回文子串均为奇数长度（如 abba → #a#b#b#a#，回文中心为第 4 位的 #）；^ 和 $，确保扩展时 t[i+p[i]+1] 和 t[i-(p[i]+1)] 不会越界，无需额外判断。mirror = 2*center - i：是 i 关于 center 的对称点（如 center=4，i=5 → mirror=3）；i < right，p[i] 初始值取 min(right-i, p[mirror])：
right-i：保证 i+p[i] 不超过当前右边界 right；p[mirror]：利用对称位置的回文长度，避免重复扩展。p[i] 扩展后仍能匹配时，才继续扩展，大幅减少重复计算。p[i]（预处理后的半径） - 1；(i - p[i]) / 2：因预处理字符串中每个原字符前都有 #，需除以 2 还原。可通过数学计算直接映射原字符串索引和预处理后的索引，避免额外存储预处理字符串：
// 空间优化版 Manacher（无需显式预处理字符串）
string manacher_optimized(const string& s) {
int n = s.size();
if (n == 0) return "";
int max_len = 0, start = 0;
int center = 0, right = 0;
vector<int> p(2 * n + 1, 0); // 对应预处理后的 p 数组
for (int i = 0; i < 2 * n + 1; ++i) {
// 计算原字符串的对称位置
int mirror = 2 * center - i;
if (i < right) {
p[i] = min(right - i, p[mirror]);
}
// 计算当前预处理位置对应的原字符串左右指针
int l = i - (p[i] + 1);
int r = i + (p[i] + 1);
// 映射到原字符串的索引：l' = l/2, r' = r/2 - 1
while (l >= 0 && r < 2 * n + 1) {
int cl = l / 2, cr = (r - 1) / 2;
if (cl >= n || cr >= n || s[cl] != s[cr]) break;
p[i]++;
l--;
r++;
}
// 更新 center 和 right
if (i + p[i] > right) {
center = i;
right = i + p[i];
}
// 更新最长回文子串
int cur_len = p[i];
if (cur_len > max_len) {
max_len = cur_len;
start = (i - p[i]) / 2;
}
}
return s.substr(start, max_len);
}
Manacher 算法可扩展为统计所有回文子串的数量（需遍历 p 数组累加）：
// 统计所有回文子串数量（基于 Manacher）
long long count_palindromes(const string& s) {
string t = preprocess(s);
int n = t.size();
vector<int> p(n, 0);
int center = 0, right = 0;
long long total = 0;
for (int i = 1; i < n - 1; ++i) {
int mirror = 2 * center - i;
if (i < right) p[i] = min(right - i, p[mirror]);
while (t[i + p[i] + 1] == t[i - (p[i] + 1)]) p[i]++;
if (i + p[i] > right) {
center = i;
right = i + p[i];
}
// 累加回文子串数量：每个 p[i] 对应 floor(p[i]/2) 个回文子串
total += p[i] / 2;
}
return total;
}
^ 和 $，导致扩展时越界访问；p[i]（正确应为 p[i]-1）；mirror 计算错误（正确应为 2*center - i）。| 算法/数据结构 | 时间复杂度 | 空间复杂度 | 核心优势 | 适用场景 |
|---|---|---|---|---|
| Manacher 算法 | O(n) | O(n) | 仅找最长回文子串，实现简单 | 最长回文子串查询 |
| 回文自动机 | O(n) | O(n) | 统计所有回文子串信息 | 回文子串数量/出现次数统计 |
| 中心扩展法 | O(n^2) | O(1) | 实现极简，无需额外空间 | 短字符串、简单场景 |
| 后缀数组 | O(n log n) | O(n) | 通用，支持多字符串回文对比 | 多字符串最长公共回文子串 |
选择建议：
bool is_palindrome(const string& s) {
string res = manacher(s);
return res.size() == s.size();
}
vector<string> find_all_palindromes(const string& s) {
string t = preprocess(s);
int n = t.size();
vector<int> p(n, 0);
int center = 0, right = 0;
vector<string> res;
for (int i = 1; i < n - 1; ++i) {
int mirror = 2 * center - i;
if (i < right) p[i] = min(right - i, p[mirror]);
while (t[i + p[i] + 1] == t[i - (p[i] + 1)]) p[i]++;
if (i + p[i] > right) {
center = i;
right = i + p[i];
}
// 提取所有以 i 为中心的回文子串
int len = p[i];
if (len > 0) {
int start = (i - len) / 2;
string sub = s.substr(start, len);
res.push_back(sub);
}
}
// 去重
sort(res.begin(), res.end());
res.erase(unique(res.begin(), res.end()), res.end());
return res;
}
注意：Manacher 算法解决的是子串问题（连续字符），最长回文子序列（非连续）需用动态规划，但可结合 Manacher 优化部分场景：
// 最长回文子序列（DP 实现，对比参考）
int longestPalindromeSubseq(const string& s) {
int n = s.size();
vector<vector<int>> dp(n, vector<int>(n, 0));
for (int i = n - 1; i >= 0; --i) {
dp[i][i] = 1;
for (int j = i + 1; j < n; ++j) {
if (s[i] == s[j]) {
dp[i][j] = dp[i + 1][j - 1] + 2;
} else {
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
}
}
}
return dp[0][n - 1];
}
Manacher 算法是解决最长回文子串问题的'最优解'，核心要点可总结为：
掌握 Manacher 算法的关键：
mirror = 2*center - i）；Manacher 算法是 C++ 算法竞赛中处理回文子串问题的基础算法，其'利用对称性减少重复计算'的思想，也可迁移到其他字符串算法的优化中。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online