01先把问题说具体
找出 'abacaba' 与 'abba' 的所有中心回文半径,为什么普通中心扩展最坏会重复检查平方次?
02一步步得到方法
先把半径的含义固定
odd[i] 表示以 i 为字符中心的奇回文半径,包含中心,长度为 2·odd[i]−1。even[i] 表示中心位于 i−1 与 i 之间的偶回文半径,长度为 2·even[i]。分开写可避免插入分隔字符的碰撞问题。
普通中心扩展在 aaaaa 这类输入中反复验证相同对称关系。Manacher 维护已经知道的最右回文 [l,r],利用其对称性复用镜像中心的半径。
镜像信息只能用到已知边界
奇中心 i 的镜像为 l+r−i,偶中心为 l+r−i+1。若 i 在 [l,r] 内,初始半径取镜像半径和到右边界距离的较小值;跨出 r 的部分必须实际比较。
扩展完成后,如果新回文伸得更右,就更新 l,r。每次超出已知边界的成功比较都会推进 r,r 只向右走 O(n) 次,因而总工作线性。
镜像半径只能复用已知对称区
当当前位置落在当前最右回文内,关于其中心的镜像点提供一个候选半径。若镜像回文完全在已知范围内,可以直接使用;若碰到右边界,只能先截到边界,再向外比较。
线性复杂度来自最右边界只会向前移动,而不是因为每个中心绝不做多次比较。奇偶回文需用分开的半径数组或可靠的间隔变换,处理结束后还要映射回原字符串位置。
03把一个小例子完全算清楚
奇回文 'abacaba';偶回文 'abba'。
| 步骤 | 计算与状态 | 为什么这样做 |
|---|---|---|
| abacaba 的中心 3 | 左右依次 c、自身外的 a、b、a | odd[3]=4,长度 7 |
| 镜像中心 5 | 对应中心 1 的半径 2 | 可在已知边界内复用 |
| abba 的间隙中心 2 | b=b,再 a=a | even[2]=2,长度 4 |
窄屏可左右滑动表格,阅读完整计算与理由。
奇数组 [1,2,1,4,1,2,1];abba 的偶数组 [0,0,2,0]。
04为什么这个方法成立
- 维护区间内字符关于中心对称,因此镜像回文在边界内仍成立。
- 取最小值只使用已证明的部分,额外比较决定未知外部范围。
- 每个中心得到最大可扩展半径,奇偶两类覆盖所有回文子串。
05把推导翻译成代码
Python · 可独立运行的教学实现
def manacher(s):
n = len(s)
odd,even = [0]*n,[0]*n
l,r = 0,-1
for i in range(n):
k = 1 if i > r else min(odd[l+r-i],r-i+1)
while i-k >= 0 and i+k < n and s[i-k] == s[i+k]:
k += 1
odd[i] = k
if i+k-1 > r:
l,r = i-k+1,i+k-1
l,r = 0,-1
for i in range(n):
k = 0 if i > r else min(even[l+r-i+1],r-i+1)
while i-k-1 >= 0 and i+k < n and s[i-k-1] == s[i+k]:
k += 1
even[i] = k
if i+k-1 > r:
l,r = i-k,i+k-1
return odd,even逐个理解关键决定
odd[l+r-i]- 奇中心关于区间中心的镜像下标。
even[l+r-i+1]- 偶中心位于字符间隙,镜像公式多 1,不能照抄奇数版本。
06时间、空间与实现范围
时间 O(n),两个半径数组 O(n) 空间;列出所有回文子串可能有 O(n²) 输出,线性半径不等于线性枚举全部内容。
按 Python 码点判断相等,字素簇回文需要预处理。
07改变条件,检查哪里会出错
只计算奇回文
会漏掉 abba、aa 等偶长度答案。
直接复制镜像半径而不截断
可能声称已知区间外也是回文,必须受 r 限制。
把镜像点完整半径无条件复制
超出已知外层回文边界的部分尚未验证,必须截断并重新扩展。
08从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
'aaaa' 有多少回文子串?
需要一点提示
所有 odd 与 even 半径相加。
查看解析与答案
odd=[1,2,2,1],even=[0,1,2,1],总计 10。
如何从 odd[i] 得到起点?
需要一点提示
半径包含中心。
查看解析与答案
起点 i−odd[i]+1,长度 2·odd[i]−1。
如何只输出最长回文?
需要一点提示
比较奇偶长度。
查看解析与答案
遍历全部中心取最大长度及对应起点,再切片一次;不必生成所有回文内容。