问题定义
给定字符串 s，找其中最长的回文子串。暴力枚举所有子串并判断回文是 O(n³)；枚举每个”中心”向外扩展，最坏 O(n²)。马拉车算法（Manacher）利用回文的对称性，把复杂度压到 O(n)。
核心思想
回文的两种中心
回文中心对称，但中心有两种形态：奇数长度（如 "aba"，中心是单个字符）和偶数长度（如 "abba"，中心在两个字符之间）。两种形态处理逻辑不同，是写起来容易出错的根源。
预处理：插入 # 统一奇偶
在字符间插入分隔符 #，首尾加哨兵 ^、$（与任何字符都不等，扩展时自动停，免去越界判断）：
原始字符串 "babad" → 处理串 "^#b#a#b#a#d#$"
原串的奇数回文仍以原字符为中心（”bab” → “#b#a#b#”），偶数回文以 # 为中心（”abba” → “#a#b#b#a#”）。之后只需要写”以某位置为中心扩展”这一种逻辑。
len 数组
len[i] = 处理串中以 i 为中心的回文半径（含中心）。由于 # 的存在，原串回文长度恰好等于 len[i]：比如 i=4 处 len=3，对应原串 “bab”（长度 3）；偶数回文 “abba” 对应 i=5 处 len=4。奇偶统一后一条公式适用。
中心与右边界：对称复用
维护当前已知”最右回文”的 center 和 right。处理 i 时若 i < right，则 i 落在已知回文内部，可以借它关于 center 的镜像点 mirror = 2*center - i 的结果初始化：
len[i] = min(right - i, len[mirror])
这行是整个算法的关键：镜像范围内的回文和已知回文对称，不用重新扩展；扩展只发生在右边界推进时，而 right 单调右移，所以每个位置至多被扩展一次。
示例走查（”babad”）
处理串 ^ # b # a # b # a # d # $（下标 0..12），逐位算 len[]：
i=1: 扩展立即失败，len=0
i=2: 扩展成 "#b#"，len=1，更新 center=2, right=3
i=3: 无法扩展，len=0
i=4: 直接扩展：t[5]=t[3]='#'、t[6]=t[2]='b'、t[7]=t[1]='#'
len=3，更新 center=4, right=7 （span 1..7 = "#b#a#b#" = "bab"）
i=5: 镜像初始化 len=min(7-5, len[3]=0)=0，无法扩展
i=6: 镜像初始化 len=min(7-6, len[2]=1)=1
再扩展：t[8]=t[4]='a'、t[9]=t[3]='#'，len=3
更新 center=6, right=9 （span 3..9 = "#a#b#a#" = "aba"）
i=8: 镜像初始化 len=min(9-8, len[4]=3)=1，无法扩展
最大 len=3 → 真实回文长度 3
start = (center - len) / 2：center=4 得 0 → "bab"；center=6 得 1 → "aba"
注意 i=6 的两次”免费扩展”来自镜像，这是暴力中心扩展做不到的。
代码实现（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 推进时，而 right 单调右移——每个字符至多被扩展一次；
- 空间 O(n)：len 数组与处理串各占 O(n)；
- 马拉车是”用预处理和对称性换时间”的典型，掌握后对理解 Z 函数、扩展 KMP 也有帮助。
