Manacher
2026-08-05
简介
Manacher 用于快速计算一个字符串内的回文子串位置。
流程
首先,由于回文子串的回文中心又可能是空隙(即偶数长度回文),我们要在原字符串每个字符之间插入标识字符,如 #,在最前面和后面插入不同的哨兵字符,如 ! 和 @。
转换完以后,我们维护当前最大回文右端点 R 以及其中心点 C,设 p[i] 表示 i 为中心最长回文的半径,处理到 i 时,[1,i) 已经计算完,我们根据 i 与 R 的关系讨论:
- 若 i>R,我们从 i 进行暴力扩展。
- 若 i≤R,由于 i 在一个回文串里,它的对称点 2C−R 已经计算出 p,又因为回文的特性,此时 p[i] 的最小取值为 min(p[2C−R],R−i),我们还需要对其进行暴力扩展,防止边界之外有匹配。
复杂度就是均摊 O(n)。
