C++怎么实现Manacher算法_C++最长回文子串【文本】

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（如中文），预处理仍可用 '#'，但需确保 '#' 不在原串中出现，否则得换分隔符（如 ''）并用 vector<char></char> 代替 string

事情说清了就结束。真正难的不是写对 Manacher，是想清楚：你手上的字符串有没有特殊字符、长度会不会爆内存、要不要支持多线程并发调用、以及——是不是真的需要这个复杂度。