Manacher算法比暴力解法快是因为其时间复杂度为O(n)，而暴力解法为O(n³)；它通过预处理和维护最右回文边界复用已有信息，避免重复比较，并需注意预处理串索引转换、边界检查及不依赖find/KMP等无关函数。
Manacher算法为什么比暴力解法快
暴力解法对每个中心点向两边扩展，时间复杂度是 O(n³)（枚举所有子串再验证），而 Manacher 算法通过预处理和维护「已知最右回文边界」，把时间压到 O(n)。关键在于它复用了之前计算过的回文信息，避免重复比较。
实际使用中，除非字符串极短（比如 len ），否则别手写三层循环——不是写不对，而是容易在边界上漏判 <code>s[i] == s[j] 或越界访问 s[j]。
Manacher 的核心预处理是插入分隔符（如 "#"），把奇偶长度统一成奇数长度处理。例如 "aba" → "#a#b#a#"，"abba" → "#a#b#b#a#"。
如何正确实现Manacher的数组初始化和边界更新
最容易出错的是 radius 数组下标和原始字符串的映射，以及 center 和 right 的更新时机。
立即学习“C++免费学习笔记（深入）”；
-
radius[i]表示以位置i为中心的最长回文半径（含中心），所以真实回文长度是radius[i]，对应原串长度为radius[i] - 1 - 当
i 时，先取镜像点 <code>j = 2 * center - i，再取radius[i] = min(radius[j], right - i)—— 这一步不能省，否则会破坏O(n)性质 - 只有在扩展成功后（即
s[i + radius[i]] == s[i - radius[i]]）才递增radius[i]；扩展失败就停，不强行加一 - 每次
i + radius[i] > right时，必须更新center = i和right = i + radius[i]，否则后续镜像失效
从Manacher结果还原原始字符串的起始位置
预处理后的字符串索引和原串不一致，直接用 i 和 radius[i] 算原串下标容易偏移。
假设预处理串为 ps，原串为 s，则：
- 预处理串中位置
i对应原串下标为(i - 1) / 2（仅当i是奇数，即对应原字符） - 最长回文在
ps中覆盖区间是[i - radius[i] + 1, i + radius[i] - 1] - 该区间内第一个原字符位置是
(i - radius[i] + 1 + 1) / 2 = (i - radius[i] + 2) / 2，但更稳妥的做法是：找出区间内最小的奇数索引start_p，然后start = start_p / 2 - 最终长度 =
radius[i] - 1，起始下标 =(i - radius[i] + 1 + 1) / 2（整除，C++ 中(x + 1) / 2等价于向下取整除2）
要不要用std::string::find或KMP辅助
完全不需要。std::string::find 解决的是子串匹配，不是回文判定；KMP 的 next 数组也不适用于回文中心扩展场景。有人试图把字符串翻转后拼接再跑 KMP，那是为「最长回文前缀/后缀」设计的，对任意位置的最长回文子串无效。
真正要警惕的是：别为了“避免手写算法”而去调用第三方库做回文检测——C++ 标准库根本没有 is_palindrome 或 longest_palindromic_substring 这类函数。自己实现 Manacher 是最可控、最高效的选择。
边界检查永远别偷懒：预处理串长度是 2 * n + 1，radius 数组大小必须至少为这个值，且访问 ps[i ± r] 前必须确认 i ± r 在 [0, ps.size()) 范围内。
