Manacher 回文半径算法

逐个中心向两侧扩张，很容易写对回文程序。但在 aaaa…a 上，相同字符会被许多中心反复比较，总时间达到二次方。Manacher 的关键是保存一个已证实的大回文，让内部中心从对称位置借用已完成的工作；借到边界时停下，只有边界外仍需比较。

形式陈述

输入、输出与区间约定

输入是长度 $n$ 的只读字符串，字符比较视为常数成本。输出奇偶回文半径 odd 与 even：odd[i]=k 代表 $[i-k+1,i+k)$ ，even[i]=k 代表 $[i-k,i+k)$ 。空输入给两份空数组。算法需 $O(n)$ 时间、 $O(n)$ 个整数单元；不把二次方个回文出现展开成列表。

两次扫描分别处理奇、偶中心。各自维护已处理中心中右端最远的回文区间 $[L,R)$ ；这里 $R$ 是不含的端点。尚无已知区间时设 $L=R=0$ 。当当前中心 $i<R$ 时，奇中心的镜像为 $j=L+R-1-i$ ，偶中心的镜像为 $j=L+R-i$ 。两个式子相差一，因为偶中心位于字符之前的间隙。

可直接运行的两个扫描

python

def manacher(s):
    n = len(s)
    odd, even = [0] * n, [0] * n
    left = right = 0
    for i in range(n):
        k = 1 if i >= right else min(odd[left + right - 1 - i], right - i)
        while i - k >= 0 and i + k < n and s[i - k] == s[i + k]:
            k += 1
        odd[i] = k
        if i + k > right:
            left, right = i - k + 1, i + k
    left = right = 0
    for i in range(n):
        k = 0 if i >= right else min(even[left + right - i], right - i)
        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 > right:
            left, right = i - k, i + k
    return odd, even

第二遍必须重新令 left=right=0：奇回文不能充当偶回文扫描的已证实外壳。本实现不用插入分隔符或哨兵，因此不要求在输入字母表之外另找字符。每个边界检查都发生在字符访问之前。

直觉

镜像信息究竟能借多少

先看奇中心。已知 $[L,R)$ 回文，里面的字符 $x$ 和 $L+R-1-x$ 相等。当前中心 $i$ 位于外壳右半边，它的镜像 $j$ 已经处理；围绕 $j$ 的每对相等字符，只要仍留在外壳内，就能再次反射成围绕 $i$ 的一对相等字符。由此得到可靠下界

\operatorname{odd}[i]\ge\min(\operatorname{odd}[j],R-i).

若 odd[j] 小于 $R-i$ ，镜像回文外的那一对失配也落在外壳内部。反射把这个失配一并搬到 $i$ 周围，所以当前半径恰为 odd[j]，无需成功扩张。代码仍做一次比较，但它会立即失败。

若 odd[j]≥ $R-i$ ，目前只能借到右边界，无法断言再外一圈是否相等。代码从字符 $R$ 开始继续比较，一直扩到首次失配或越界。这里必须取 min；直接复制镜像的完整半径，可能把旧外壳之外未经核验的字符也当成匹配。

偶中心的论证相同，但反射的是间隙。外壳 $[L,R)$ 的中心为 $(L+R)/2$ ，故 $i$ 的镜像是 $L+R-i$ 。半径 $k$ 已覆盖 $[i-k,i+k)$ ，下一对字符是 $i-k-1$ 与 $i+k$ ，不是奇中心公式中的 $i-k$ 。

奇中心位于已知回文内部，镜像半径只可借到右边界，边界外的比较仍须执行 — 由 i=7 查询镜像 j=1；只借半径1，再比较右边界外的字符

为什么更新区间保持正确

把循环不变量写成三件事：所有小于 $i$ 的中心半径已正确； $[L,R)$ 确实回文； $R$ 是这些中心能达到的最大右端点。初始化满足空情况。镜像步骤给可靠下界，扩张补齐当前半径；若新右端更远，就用刚核验的整个区间替换旧外壳。因此三件事在下一轮仍成立。

最大右端相同而不替换旧区间也正确，不要求 $L$ 最小。偶扫描遇到零半径时还可能保存空区间 $[i,i)$ ；下一中心已在其右侧，代码会重新从零开始，不会错误复用空回文。

例子与边界

复算一个镜像不足以决定答案的位置

取 abacdcabba。奇扫描到 $i=4$ 的 d 时，初始半径一；依次比较位置 $3/5$ 的 c/c、 $2/6$ 的 a/a、 $1/7$ 的 b/b，得到半径四；再比较 $0/8$ 的 a/b 失败。保存外壳 $[1,8)$ ，内容是 bacdcab。

处理 $i=6$ 时，镜像 $j=1+8-1-6=2$ ，odd[2]=1，小于 $R-i=2$ 。旧失配完全在外壳内，故 odd[6]=1。处理 $i=7$ 时，镜像 $j=1$ ，odd[1]=2，但 $R-i=1$ ，只能复制半径一。新比较 $6/8$ 是 a/b，因此半径停在一；若直接复制二就会错误报告 abb 为回文。

偶扫描到间隙 $i=8$ ，先比较 $7/8$ 的 b/b，再比较 $6/9$ 的 a/a，得到 even[8]=2，区间 $[6,10)$ 即 abba。下一圈右端越界而停止，不是字符失配。最后数组与回文半径页的表逐项一致，总出现数十六。

看起来小的下标偏差会漏掉整类输入

aa 的偶数组应为 $[0,1]$ ，而奇数组为 $[1,1]$ 。若把 even 的镜像误写成奇镜像式，或者从半径一开始偶扩张，可能跳过必要的相邻字符检验。ab 必须得到 even=[0,0]，不能因初始化就承认长二回文。

算法按字符相等工作，不用字典序；把字符换成可常数时间比较的整数仍可使用。若比较本身要扫描可变长对象，总复杂度应改为字符比较次数乘相应代价。文本追加字符后，旧中心的最终半径还可能增长；本页函数处理一份固定全文，不能把已返回数组当作追加后仍自动正确的索引。

推论与应用

成功比较与失败比较分别记账

用摊还分析核算一次扫描。镜像半径严格落在外壳内时，下一次比较若发生便是已知失配，没有成功扩张。其余情况下，每次新成功比较都让当前回文的右端越过原来的最远边界一格；全程右边界只向右移动，故这类成功比较合计至多 $n$ 次。

失败字符比较不推动边界，却每个中心至多一次，因为一次失败就结束当前 while。边界越界同样终止循环，不会再读字符。于是每遍最多线性次成功比较、线性次失败比较及线性次初始化，两遍总计 $O(n)$ 。不能把证明简化成“每次比较都推进右端”，因为刚才位置七的失配就是反例。

从数组交付可核验结果

计算最长回文、回文出现总数或单区间查询，都可直接使用半径页公式。对 abacdcabba，应交付两份十项数组、出现数十六、最长区间 $[1,8)$ 及对应文本；若任务改成全部出现，额外输出成本必须按实际区间数计入。

本单元核验程序把两份数组导出的每个区间判断与逐字符反转 oracle 对照，并检查空串、单字符、奇偶混合、全相同字符及 Unicode 码点输入。迁移练习用 bbaabbaabbaa：奇半径全为一，偶半径为 $[0,1,0,3,0,5,0,5,0,3,0,1]$ ，总出现数三十；能解释偶中心五与七各自为何只能扩到五，才不只是抄下一张数组。

参考资料

Glenn K. Manacher, “A New Linear-Time ‘On-Line’ Algorithm for Finding the Smallest Initial Palindrome of a String”, Journal of the ACM 22(3), 1975, pp. 346–351，DOI。原论文标题对应初始回文问题，本文呈现现代的全中心半径形式。
Gabriele Fici, Travis Gagie, Juha Kärkkäinen and Dominik Kempa, A Subquadratic Algorithm for Minimum Palindromic Factorization, 2014，§1：从原算法到最大中心回文线性表示的文献脉络。
KTH Competitive Programming, KACTL: Manacher.h：另一份奇偶半径实现。其奇半径不计中心、索引约定与本文不同，不能逐项照搬结果；本文代码按半开区间独立组织。

形式陈述 ​

输入、输出与区间约定 ​

可直接运行的两个扫描 ​

镜像信息究竟能借多少 ​

为什么更新区间保持正确 ​

复算一个镜像不足以决定答案的位置 ​

看起来小的下标偏差会漏掉整类输入 ​

成功比较与失败比较分别记账 ​

从数组交付可核验结果 ​

反向链接