Manacher算法通过回文半径数组p和最右覆盖回文（center/right）实现O(n)时间复杂度，核心是利用对称性复用已知半径并谨慎处理边界；预处理串中需正确映射回原串索引，空串需特判；实际应用中应权衡复杂度与需求。
Manacher算法核心思想：用回文半径数组 p 替代暴力扩中心
Manacher不是靠反复判断子串是否回文，而是维护一个“当前覆盖最右的回文”（记为 center 和 right），利用回文对称性，尽可能复用已算出的回文半径。关键在：当新位置 i 落在 right 内时，先取镜像位置 2 * center - i 的半径，再尝试向外扩展。
常见错误是没处理好边界——比如忘记 p[i] 初始值至少为 1（单字符本身是回文），或扩展时越界未检查 i - p[i] >= 0 && i + p[i] 。
-
p数组长度应为2 * n + 1（插入分隔符后总长），索引对应预处理后的字符串 - 预处理字符串推荐用
'#'插入，如"abba"→"#a#b#b#a#"，这样所有回文长度都为奇数，统一逻辑 - 原始字符串中回文起始位置 =
(i - p[i]) / 2，长度 =p[i]（注意：这是预处理串中的半径，对应原串长度就是p[i]）
C++实现中必须小心的边界和索引转换
预处理后字符串长度变长，但你不能直接拿 p[i] 当原串长度用。比如 p[i] == 5 表示预处理串中以 i 为中心、半径为 5 的回文，实际覆盖 11 个字符，其中 5 个是 '#'，6 个是原字符——所以原回文长度就是 p[i]。
容易踩的坑：用 std::string 拼接预处理串时，忘了预留空间导致频繁重分配；或用 vector<int></int> 初始化 p 时大小写错，比如写成 n 而非 2 * n + 1，后续访问越界不报错但结果随机。
立即学习“C++免费学习笔记（深入）”；
- 预处理建议用
res.reserve(2 * s.size() + 2)提前分配内存 -
p数组初始化为全 0，大小为len = 2 * n + 1 - 循环中更新
right和center的条件是i + p[i] > right，不是>=—— 等号会导致重复覆盖，破坏对称性前提
为什么不用 std::string::substr 直接返回结果
Manacher本身只负责找出最长回文的长度和中心位置，substr 是额外操作。但这里容易出问题：如果你用预处理串的 i 和 p[i] 直接调 substr(i - p[i] + 1, 2 * p[i] - 1)，拿到的是带 '#' 的串，不是原串子串。
正确做法是算出原串索引：start = (i - p[i]) / 2，len = p[i]，然后 s.substr(start, len)。注意整除是向下取整，而 i - p[i] 总是偶数（因为预处理串中有效字符都在偶数位），所以没问题。
- 不要在循环里反复调
s.substr()找最大——先记录max_len和max_center，最后算一次 - 如果输入为空串，预处理后是
"#"，p[0] == 1，此时(0 - 1) / 2 == -0.5 → 截断为 0，但s.substr(0, 1)会抛异常，得单独判空 - 多解时（多个相同最长回文），算法默认返回第一个出现的，无需额外逻辑
性能对比：Manacher vs 中心扩展 vs 动态规划
Manacher是严格 O(n)，但常数比朴素中心扩展大；DP是 O(n²) 空间+时间，实际在小数据上可能更快（cache友好）。别为了“理论上最优”硬套Manacher——除非你明确要在线性时间内处理 10⁵ 级别字符串。
真实场景中，90% 的回文需求（比如校验、简单提取）用中心扩展就够了：写法简单、易调试、无预处理开销。Manacher真正有用的地方是高频查询（如配合后缀数组）、流式处理或嵌入式资源受限环境（省掉 DP 的 O(n²) 内存）。
- Manacher的
O(n)依赖于每个字符最多被扩展一次，一旦写错边界检查（比如漏了i - p[i] >= 0），就退化成O(n²) - g++ 编译时加
-O2对p数组的连续访问有明显优化，但别指望它帮你修复逻辑错误 - 如果字符串含 Unicode（如中文），预处理仍可用
'#'，但需确保'#'不在原串中出现，否则得换分隔符（如'\0'）并用vector<char></char>代替string
事情说清了就结束。真正难的不是写对 Manacher，是想清楚：你手上的字符串有没有特殊字符、长度会不会爆内存、要不要支持多线程并发调用、以及——是不是真的需要这个复杂度。
