Manacher · 回文半径

Manacher：最长回文子串的线性算法

最长回文子串的问题是：在串 $s$ 里找出最长的一段正读反读相同的连续子串。Z function 一页把「记住已匹配到的最右边界，新位置先抄镜像算好的值」用在了前缀匹配上，本页把同一套记账法用到回文上，得到 Manacher 算法。动手之前还要跨过一道坎：回文分奇数长与偶数长两种，中心的形态不同，朴素写法得分两路走。

1 · 中心扩展的代价

每个回文都有唯一的中心：长度为奇数时中心是一个字符，长度为偶数时中心是两个字符之间的缝，长为 $n$ 的串因此共有 $2n - 1$ 个中心。枚举中心、向两侧同步扩张到字符不等或撞上边界为止，就得到以该中心为轴的最长回文；全部中心取最大者即为答案。

这个写法的代价是 $O(n^2)$ ，单个中心最多扩 $n / 2$ 步。浪费的地方在于每个中心都从零起扩，上一个中心确认过的相等关系随即作废。全同串 aaaa…a 是最坏的样子：中心 $c$ 一路扩到边界，而它左右的那些字符对，早在中心 $c - 1$ 的扩张里就比过一遍。

图 1-1 · 朴素中心扩展。绿色是当前中心已确认的回文区间，浅蓝是迄今最长的一段，读数给出中心总数与累计字符比较次数。可把输入改成全同串观察比较次数的增长。

2 · 分隔符变换与奇偶的统一

奇偶两种中心之所以碍事，是因为它们在数组下标上没有统一的表示。往每两个字符之间以及首尾各插一个分隔符，长为 $n$ 的串就变成长 $2n + 1$ 的串 $t$ ：原字符落在奇数位，分隔符落在偶数位。abacaba 变成 #a#b#a#c#a#b#a#。

变换之后每个回文都以 $t$ 的某个下标为中心，原来的奇数长回文对应奇数位中心，偶数长回文对应偶数位中心，两路并成一路。定义 $t$ 上以 $i$ 为中心的回文半径 p[i] 为单侧能延伸的字符数（不含中心自身），那么 p[i] 直接就是它在原串上对应的那个回文的长度，起点是 $(i - p[i]) / 2$ ：回文两端在 $t$ 上必定各是一个分隔符，半径里原字符与分隔符恰好各占一半。

注 · 常见的提醒是「分隔符要挑一个原串里没有的字符」，在这个变换里它是多余的。镜像下标 $2c - i$ 与 $i$ 奇偶相同，扩张时比较的 $i - k$ 与 $i + k$ 奇偶也相同，于是分隔符槽只跟分隔符槽相比、原字符只跟原字符相比，两类下标之间不存在任何一次比较。把 a 与 # 两个字符组成的、长度不超过 10 的全部串跑一遍，分隔符取 # 时结果全对；把分隔符换成串里就有的 a，ab 两个字符组成的、长度不超过 11 的全部串同样全对，manacher.test.ts 钉住了这两组。相比之下，Z function §3 里拼接用的那个分隔符是真的不能撞车，两处的「分隔符」承担的职责并不一样。

3 · 最右回文边界下的半径复用

求半径数组 p[] 时另外维护一对量：已知回文中右端最靠右的那个，记它的中心为 $c$ 、右端为 $r$ ，称作最右回文。新的中心 $i$ 落在这个区间之内时，它关于 $c$ 的镜像 $2c - i$ 的半径早已算好，而区间内的字符两侧逐位对称，所以 p[i] 可以先取 min(r - i, p[2 * c - i])，只对伸出右端的那部分做真比较。

复杂度的论证与 Z function §2 逐字对应：每一次成功的比较把 $r$ 往右推一格， $r$ 单调不减且不超过 $2n + 1$ ；每个中心至多贡献一次失败比较，中心共 $2n + 1$ 个。两项相加是线性的。Z-box 在本页换成了最右回文，区间端点 $[l, r)$ 换成了中心与右端这一对，min 的两项换成边界余量与镜像半径，其余一字未改。

图 3-1 · Manacher 在变换串上逐个中心求半径。绿色是当前最右回文，标 c 与 r 的两格是它的中心与右端，蓝色格是本步抄来的镜像半径。可对照图 1-1 的比较次数读数。

警示 · 两处的 min 都写成 min(r - i, …)， $r$ 的含义却不同。Z-box 是右开区间 $[l, r)$ ，那里的 r - i 数的是从 $i$ 起到区间末尾的字符个数；本页的 $r$ 是闭区间的右端，r - i 数的是从 $i$ 往右还能延伸的格数，不含 $i$ 自己。半径本来就不含中心，两个口径正好错开一位。把一处的循环直接抄到另一处而不改 $r$ 的含义，得到的是一个整体偏移一格的数组，core/z-function.ts 与 core/manacher.ts 里的注释各自写明了自己的口径。

4 · 比较次数的实测

线性不等于更快。把两条实现放在同一个字符比较计数下（朴素在原串上比，Manacher 在长 $2n + 1$ 的变换串上比），三组输入给出三种结论：

全同串： $n$ 取 8 / 16 / 32 / 64 时，朴素分别用 28 / 120 / 496 / 2016 次比较，Manacher 用 15 / 31 / 63 / 127 次，差距随 $n$ 张开。
交替串 abab…： $n = 8$ 时朴素 19 次、Manacher 21 次； $n = 10$ 时朴素 29 次、Manacher 27 次。交叉点落在 $n = 10$ 。
随机串：三字母表上长 160 的 200 个串，朴素平均 471.2 次，Manacher 平均 588.3 次，朴素反而更省。

第三组是写本页时才量出来的，原先以为随机输入上两者至少打平。随机串上绝大多数中心扩一两步就撞上不等，朴素的实测代价本来就接近线性；而 Manacher 的中心有 $2n + 1$ 个，每个中心至少付一次失败比较，常数就此吃亏。 $O(n^2)$ 与 $O(n)$ 的差别只在回文密集的输入上兑现。三组数字都由 manacher.test.ts 钉住。

建议 · 输入是自然文本、又只要一个最长回文时，朴素中心扩展的实测代价与 Manacher 同量级而常数更小，多出来的实现复杂度未必划算。Manacher 值得用在两处：输入可能被构造成回文密集的形态，以及需要的是全部半径而不只是最大值，例如逐位置回答「以这个位置为中心的最长回文有多长」。若问题问的是全部子串而非全部回文，另有一条路，见 suffix automaton。

5 · 参考文献

Manacher, G. (1975). A new linear-time "on-line" algorithm for finding the smallest initial palindrome of a string. Journal of the ACM, 22(3), 346–351.
Gusfield, D. (1997). Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge University Press.