Manacher算法需预处理为"^#a#b#a#$"格式，rad[i]表示含中心的回文半径，左边界为i−rad[i]+1；数组大小至少2n+5，更新时取min(rad[j], r−i+1)；还原原串位置用start=(i−rad[i]+1)/2、len=rad[i]−1。
Manacher算法在C++里怎么写才不越界
Manacher算法核心是预处理字符串、维护回文半径数组 rad[] 和中心位置 mid，但新手常卡在边界计算上——比如用 i - rad[i] 当左边界时没考虑 rad[i] 是“包含中心的长度”，实际左边界该是 i - rad[i] + 1；或者预处理插入的分隔符（如 '#'）导致原串下标映射出错。
实操建议：
立即学习“C++免费学习笔记（深入）”；
- 预处理统一用
"^#a#b#a#$"形式：开头加'^'、结尾加'$'，避免边界判断；中间每个字符前后都插'#'，这样所有回文长度必为奇数，rad[i]直接表示以i为中心的回文半径（含中心） -
rad数组大小至少为2 * n + 5（n是原串长），别只开n+1 - 更新
rad[i]时，若i （<code>r = mid + rad[mid] - 1），先取对称点j = 2 * mid - i，再取rad[i] = min(rad[j], r - i + 1)—— 注意是r - i + 1，不是r - i
为什么不能直接用string::substr暴力找最长回文
因为时间复杂度是 O(n³)：两层循环枚举端点，再一层验证是否回文。而 Manacher 是 O(n)，关键在利用已算过的回文信息跳过重复比较。
实操建议：
立即学习“C++免费学习笔记（深入）”；
- 当输入长度
n > 1e5时，暴力法必然超时；Manacher 在n = 1e6下仍稳定运行 - 如果只要判断是否存在长度 ≥ k 的回文，不用存所有
rad[i]，边算边比rad[i] >= k即可，省空间 - 注意：Manacher 找的是“最长回文子串”，不是“最长回文子序列”——后者要用 DP，别混
C++里char数组和string混用容易崩在哪
常见错误是把 std::string 直接传给期望 const char* 的函数（比如 strlen()），或用 string.c_str() 后又修改了原 string，导致指针悬空。
实操建议：
立即学习“C++免费学习笔记（深入）”；
- Manacher 预处理推荐用
std::string构造新串，比如：string t = "^"; for (char c : s) { t += '#'; t += c; } t += "#$"; - 若坚持用
char[]，务必手动补'\0'，且分配长度 ≥2 * s.size() + 5，否则strlen()或越界读 - 别在循环里反复调用
s.length()——虽然现代编译器会优化，但明确写成变量更稳：int len = t.length();
如何从rad[]还原原始串里的最长回文位置
rad[i] 对应的是预处理串中以 i 为中心、长度为 rad[i] 的回文。要转回原串下标，得反向映射：预处理串中位置 i 对应原串字符位置是 (i - 1) / 2（因为 ^#a#b#a#$ 中，a 出现在索引 2、4、6…）
实操建议：
立即学习“C++免费学习笔记（深入）”；
- 找到最大
rad[i]后，计算原串起始位置：start = (i - rad[i] + 1) / 2，长度：len = rad[i] - 1（因为每个原字符被'#'包围，真实长度 = 半径 - 1） - 如果原串含中文或 UTF-8 多字节字符，Manacher 会失效——它按字节操作，不是按 Unicode 字符。此时必须先转为宽字符或用其他算法
- 多个相同最大长度时，
rad[i]第一次出现最大值的位置对应最左解，无需额外排序
最易被忽略的是预处理串的边界字符 '^' 和 '$'：它们不只是占位符，更是让 while 循环不必每轮都判边界的关键——少写一个，rad[i] 就可能越界访问。
