manacher算法能线性时间的关键在于利用已知回文信息复用right边界，避免重复扩展；通过center和right维护最右回文，结合对称点j的p[j]值进行下界估计，并仅在必要时暴力扩展，且right单调不减，总扩展次数≤n。
Manacher 算法为什么能线性？关键在 right 边界复用
它不是靠暴力扩，而是靠已知回文信息“跳过”重复计算。核心维护两个变量：center（当前最右回文的中心）和 right（该回文最右位置）。当处理新位置 i 时，若 i ，就能利用对称点 <code>j = 2 * center - i 的回文半径 p[j] 做下界估计——这步省掉了大量中心扩展。
- 如果
p[j] ，说明 <code>j的回文完全落在以center为中心的回文内，那么i的回文半径直接等于p[j]，无需扩展 - 如果
p[j] >= right - i，说明j的回文碰到了左边界，i的半径至少是right - i，但可能更大，必须从right + 1开始继续暴力扩展 - 每次扩展成功都会更新
right和center，而right只增不减，总扩展次数 ≤ n
预处理字符串：为什么加 '#'？
原始字符串如 "aba" 和 "abba" 的回文中心类型不同（奇/偶），统一处理很麻烦。Manacher 标准做法是插入分隔符，变成 "#a#b#a#" 或 "#a#b#b#a#"，这样所有回文长度都为奇数，中心恒为单个字符。
- 常用预处理：对每个字符前后加
'#'，首尾再补一个不同字符（如'^'和'$'）避免越界判断 - 例如
s = "ab"→t = "^#a#b#$"，长度变为2 * n + 3 -
t[i]是'#'时，对应原串中字符间隙；是字母时，对应原串字符本身 - 最终回文长度 =
p[i] - 1（因为每个真实字符被两个'#'包围，多算了一次）
p[i] 数组怎么初始化和更新？
p[i] 表示以位置 i 为中心的最长回文半径（包含中心，即回文串长度为 2 * p[i] - 1）。它不是“从 i 往左右各扩多少”，而是“整个回文覆盖了多长”。
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
- 初始化
p[0] = 0，center = right = 0 - 遍历
i从1到len(t)-2（避开首尾哨兵） - 若
i ，设 <code>j = 2 * center - i，取p[i] = min(p[j], right - i)（注意是right - i，不是right - i + 1） - 然后执行
while (t[i + p[i]] == t[i - p[i]]) p[i]++—— 这里下标必须保证不越界，所以预处理加哨兵很重要 - 若
i + p[i] > right，则更新center = i，right = i + p[i]
常见错误：边界、索引、长度转换全在 '#' 上翻车
90% 的实现 bug 出在预处理和结果还原环节，不是算法逻辑错。
- 忘记在
t首尾加不同哨兵（如'^'和'$'），导致 while 扩展时数组越界 - 误把
p[i]当作“向右扩展长度”，实际它是“半径”，原串中对应回文长度是p[i] - 1 - 找最大
p[i]后，没换算回原串起始位置：原串起点索引 =(i - p[i]) / 2（因为t中每两个位置对应原串一个字符） - 使用
std::string::at()而非[]，触发边界检查异常；或用vector<char></char>但忘了预留空间
最易忽略的是：right 更新必须严格满足 i + p[i] > right 才触发，等于不行；且 p[i] 在 while 后已经多加了 1，所以比较时直接用它即可。这个细节错一点，整个线性时间保障就崩了。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
