问题定义
给定一个字符串 s，找出其中最长的回文子串。暴力解法枚举所有子串并逐一判断是否为回文，时间复杂度为 O(n³)；即使枚举每个”中心”再向外扩展，最坏也是 O(n²)。马拉车算法（Manacher’s Algorithm）利用回文的对称性，把这个问题优化到了 O(n)。
核心思想
回文的两种类型
回文是中心对称的，但中心有两种形态：
- 奇数长度：如
"aba"，中心是单个字符b； - 偶数长度：如
"abba"，中心位于两个字符b之间。
两种形态处理逻辑不同，是写起来容易出错的根源。
预处理：统一奇偶长度
在原始字符串的每个字符之间插入特殊分隔符 #，并在首尾加上不同的哨兵字符（如 ^ 和 $）避免边界检查：
原始字符串 "babad" → 预处理后 "^#b#a#b#a#d#$"
这样处理后，原串的奇数回文变成以 # 为中心，偶数回文变成以原字符为中心——奇偶两种情况被统一了，后续只需要处理”以某个位置为中心扩展”这一种逻辑。
关键步骤
len[] 数组的含义
定义 len[i] 为预处理串中第 i 个字符为中心的最长回文半径（包含中心自身）。由于插入了分隔符，真实回文长度 = len[i] – 1。例如 len[i] = 4 对应的实际回文长度为 3。
维护对称性：center 与 right
用 center 和 right 记录当前已知的”最右回文子串”的中心和右边界。处理位置 i 时，如果 i < right，说明 i 在已知回文内部，可以借助它关于 center 的对称点 mirror = 2 * center - i 的信息快速初始化：
len[i] = min(right - i, len[mirror])
这一行是整个算法的精华——它保证了每个位置最多只被真正”扩展”一次，从而把复杂度压到线性。
中心扩展与更新
- 从
i向两侧扩展，直到字符不相等，得到最终的len[i]； - 若扩展后的右边界
i + len[i]超过了当前的right，则更新center = i、right = i + len[i]。
示例：以 “babad” 为例
预处理后：^ # b # a # b # a # d # $，逐位计算 len[]：
i=1: 边界字符，len=0
i=2: 扩展成 b#b，len=3，更新 center=2, right=5
i=3: 无法扩展，len=0
i=4: 对称初始化 len=min(5-4, len[2])=1，扩展成 a#b#a，len=4，更新 center=4, right=8
i=5: 无法扩展，len=0
i=6: 对称初始化 len=min(8-6, len[4])=2，扩展成 b#a#b，len=4，i+len=10 未超过 right，不更新
i=7: 无法扩展，len=0
最大 len = 4，真实回文长度 = 4 − 1 = 3。起点换算：start = (center - len) / 2，取 i=4 得 (4-4)/2 = 0，即原串的 "bab"（取 i=6 则得到 "aba"，两者都是最长回文）。
代码实现（C++）
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
string longestPalindrome(string s) {
if (s.empty()) return "";
// 预处理：插入 # 并在首尾加哨兵
string t = "^";
for (char c : s) { t += '#'; t += c; }
t += "#$";
int n = t.size();
vector<int> len(n, 0);
int center = 0, right = 0;
int max_len = 0, max_center = 0;
for (int i = 1; i < n - 1; i++) {
int mirror = 2 * center - i;
if (i < right)
len[i] = min(right - i, len[mirror]);
// 中心扩展（哨兵保证不会越界）
while (t[i + len[i] + 1] == t[i - len[i] - 1])
len[i]++;
if (i + len[i] > right) {
center = i;
right = i + len[i];
}
if (len[i] > max_len) {
max_len = len[i];
max_center = i;
}
}
int start = (max_center - max_len) / 2;
return s.substr(start, max_len);
}
复杂度与总结
- 时间复杂度 O(n)：每个字符最多被访问常数次——对称初始化直接复用结果，真正的扩展只发生在右边界推进时，而 right 只会单调向右移动。
- 空间复杂度 O(n)：len 数组与预处理串各占 O(n)。
马拉车算法是”用预处理和对称性换时间复杂度”的经典例子，掌握它对理解其他字符串算法（如 Z 函数、扩展 KMP）也很有帮助。
