专题进阶 · 字符串算法推荐总顺序 · 第 87 / 148 课

利用回文镜像和最右边界计算奇偶半径,避免逐中心重复扩展。

先学会这些,再进入本课 字符串 双指针 Z 算法
还有 3 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 字符串算法

ManacherManacher

利用回文的镜像半径与最右边界,在线性时间内计算所有中心的回文半径。

建议 45 分钟 · 含手算、代码与三层练习

本课要建立的能力

利用回文镜像和最右边界计算奇偶半径,避免逐中心重复扩展。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

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、aodd[3]=4,长度 7
镜像中心 5对应中心 1 的半径 2可在已知边界内复用
abba 的间隙中心 2b=b,再 a=aeven[2]=2,长度 4

窄屏可左右滑动表格,阅读完整计算与理由。

奇数组 [1,2,1,4,1,2,1];abba 的偶数组 [0,0,2,0]。

04为什么这个方法成立

  1. 维护区间内字符关于中心对称,因此镜像回文在边界内仍成立。
  2. 取最小值只使用已证明的部分,额外比较决定未知外部范围。
  3. 每个中心得到最大可扩展半径,奇偶两类覆盖所有回文子串。

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从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

'aaaa' 有多少回文子串?

需要一点提示

所有 odd 与 even 半径相加。

查看解析与答案

odd=[1,2,2,1],even=[0,1,2,1],总计 10。

练习 2 · 边界与辨析

如何从 odd[i] 得到起点?

需要一点提示

半径包含中心。

查看解析与答案

起点 i−odd[i]+1,长度 2·odd[i]−1。

练习 3 · 变式与迁移

如何只输出最长回文?

需要一点提示

比较奇偶长度。

查看解析与答案

遍历全部中心取最大长度及对应起点,再切片一次;不必生成所有回文内容。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

Princeton · 字符串算法

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。