Manacher算法通过预处理将字符串统一为奇数长度回文，利用对称性和已知回文半径数组P，在O(n)时间内求出最长回文子串；遍历中维护最右边界right和中心center，借助mirror减少重复扩展，最后根据P数组最大值定位原串起始位置并返回结果。
Manacher算法能在O(n)时间内找出字符串中最长回文子串，比暴力和动态规划更高效。C++实现的关键是预处理字符串并维护回文半径数组。
预处理字符串
在原字符串每个字符间插入特殊符号（如'#'），并在首尾添加不同边界符，避免越界。例如 "aba" 变为 "^#a#b#a#$"。
这样做可以把奇偶长度回文统一处理，所有回文都变为奇数长度。
维护回文半径数组 P
定义数组 P[i] 表示以位置 i 为中心的最长回文半径（不包含中心）。同时维护最右回文边界 right 和对应中心 center。
立即学习“C++免费学习笔记（深入）”；
遍历每个位置 i：
- 如果 i 在 right 内，利用对称性：P[i] = min(right - i, P[2 * center - i])
- 尝试向外扩展，更新 P[i]
- 如果 i + P[i] > right，更新 center 和 right
提取最长回文
扫描 P 数组找到最大值及其位置，再映射回原字符串。
原串中起始位置为 (maxCenter - maxLen) / 2，长度为 maxLen。
以下是一个完整可运行的 C++ 实现：
#include <iostream>
#include <vector>
#include <string>
using namespace std;
string longestPalindrome(string s) {
if (s.empty()) return "";
// 预处理字符串
string transformed = "^#";
for (char c : s) {
transformed += c;
transformed += '#';
}
transformed += '$';
int n = transformed.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 (i < right) {
P[i] = min(right - i, P[mirror]);
}
// 尝试扩展
while (transformed[i + P[i] + 1] == transformed[i - P[i] - 1]) {
P[i]++;
}
// 更新中心和右边界
if (i + P[i] > right) {
center = i;
right = i + P[i];
}
}
// 找最长回文
int maxLen = 0, maxCenter = 0;
for (int i = 1; i < n - 1; i++) {
if (P[i] > maxLen) {
maxLen = P[i];
maxCenter = i;
}
}
int start = (maxCenter - maxLen) / 2;
return s.substr(start, maxLen);
}
// 测试
int main() {
string s = "babad";
cout << longestPalindrome(s) << endl; // 输出 bab 或 aba
return 0;
}基本上就这些。核心是利用已知回文的对称性减少重复计算，达到线性时间复杂度。
