C++ Manacher 算法：原理、实现与应用
Manacher 算法（马拉车算法）是专门解决最长回文子串问题的线性时间算法，由 Glenn Manacher 在 1975 年提出。它通过对字符串进行预处理（插入特殊字符）消除奇偶回文的差异，并利用'回文对称性'记录已遍历区域的信息，避免重复计算，将时间复杂度从中心扩展法的 O(n^2) 降至 O(n)。本文将从核心原理、预处理、算法流程到实战优化，全面解析 Manacher 算法的设计思想与 C++ 实现技巧。
一、Manacher 算法的核心背景与优势
1.1 问题引入：中心扩展法的瓶颈
最长回文子串的经典解法是中心扩展法：遍历每个字符（奇数长度回文的中心）和每两个字符之间的间隙（偶数长度回文的中心），向两边扩展直到字符不匹配。
// 中心扩展法示例（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 - ) / ;
}
}
s.(start, max_len);
}
