lessons/课程/04-KMP与Manacher/02-Manacher回文半径与区间计数.md

Manacher：在线性时间扩展全部回文中心

本节目标

学完后，你应能分别维护奇、偶回文半径，解释镜像半径何时可以复用，在线性时间求最长回文，并把半径数组转换成回文的起点/终点计数解决区间相交问题。

前置知识与课前自测

前置：字符串下标、回文定义、区间差分。

1. 只枚举中心并向两侧扩展，最坏复杂度是多少？给出达到最坏的字符串。
2. 偶数长度回文的“中心”落在哪个字符上？
3. 已知中心 $i$ 的最大半径为 $d$，它代表一个回文还是 $d$ 个回文？

自测答案

1. $O(n^2)$；例如全部字符相同。 2. 落在两个字符之间，因此必须单独约定中心下标。 3. 代表同一中心下半径 $1..d$ 的 $d$ 个回文（偶回文从半径 1 开始，半径 0 表示不存在）。

问题动机：中心扩展哪里重复

若已知区间 $[l,r]$ 是当前最靠右的回文，并处理 $i\le r$，$i$ 关于中心的镜像位置已计算过。镜像回文完全落在 $[l,r]$ 内的部分无需再次比较；只有越过 $r$ 后才需要继续扩展。

Manacher 把每次扩展的新字符“记账”给右边界 $r$：成功越过旧 $r$ 会让 $r$ 增加，而 $r$ 全程最多增加 $n$ 次；镜像初始化与失败比较每个中心常数次，所以总时间 $O(n)$。

两套半径定义

为避免插入分隔符带来的边界混乱，课程使用两数组版本：

• d1[i]：奇回文半径数，最大区间为 $[i-d1[i]+1, i+d1[i]-1]$，长度 $2d1[i]-1$；单字符时为 1。
• d2[i]：中心在 i-1 与 i 之间的偶回文半径，最大区间为 $[i-d2[i], i+d2[i]-1]$，长度 $2d2[i]$；不存在时为 0。

停顿：字符串 abba 的 d2[2] 是多少？区间端点是什么？

答案

`d2[2]=2`，最大区间为 `[0,3]`。这里中心下标取右半部分的第一个位置。

核心算法与正确性

处理奇回文时，若 $i>r$ 从半径 1 开始；否则用镜像 l+r-i 的半径与 r-i+1 取较小值。较小值以内的字符相等由当前大回文保证；再朴素扩展，并在越过 $r` 时更新 $[l,r]$。

偶回文：若 $i>r$ 从半径 0 开始；否则用镜像 l+r-i+1 的半径与 r-i+1 取较小值，再朴素扩展。镜像下标偏一是因为偶回文的端点比奇回文多一格"半个字符"。

算法不会高估：镜像只复制已被外层回文覆盖的相等关系，越界部分仍逐字符验证。也不会低估：初始化后持续扩展直到首个失配或边界，因此得到最大半径。右边界的摊还论证给出 $O(n)$ 时间，两个数组占 $O(n)$ 空间。

实现指南

最常见错误不是公式不会背，而是混用定义：

• 明确 r 是包含式右端点；
• 奇半径初值是 1，偶半径初值是 0；
• 写出区间公式后再推镜像，不要从另一份“加分隔符模板”搬常数；
• 空串若可能出现需特判，本节题面均为非空。

精选例题 1：Palindrome

来源信息与题意

• VJudge：POJ-3974 Palindrome
• 原来源：Seventh ACM Egyptian National Programming Contest
• 大致难度：Manacher 模型建立；考点：奇偶回文、最长长度

最多 30 组小写字符串，每串长度不超过 $10^6$，END 结束。对每组输出最长回文子串长度。

Hint 1

分别计算 `d1` 与 `d2`，不要漏掉偶回文。

Hint 2

答案是所有 `2*d1[i]-1` 与 `2*d2[i]` 的最大值。

Observations、Editorial 与证明

一次 Manacher 得到每个奇、偶中心的最大半径。任意回文都有唯一中心，且被对应最大半径覆盖；枚举两数组长度能取到全局最优。反之数组中每个候选都经过字符比较验证，确为回文。每组时间、空间均为 $O(n)$。

核心伪代码与参考实现附件

d1 = odd_palindrome_radii_by_Manacher(s)
d2 = even_palindrome_radii_by_Manacher(s)
answer = max(max(2*d1[i]-1), max(2*d2[i]))
output answer

完整 GNU C++17 参考实现见附件：POJ-3974.cpp

复盘与变式

HDU-3068 最长回文 是同模型题，可用于独立复写。若要求输出一个最长回文的位置，记录产生最大长度的中心，再用半径公式还原左右端点。

灵活性实验室：Palisection

来源信息与题意

• VJudge：CodeForces-17E Palisection
• 原题：Codeforces Beta Round 17
• 难度：2900；考点：Manacher 半径转区间计数、补集计数

给长度 $1\le n\le2\times10^6$ 的小写串。每个回文出现由其起止位置唯一标识；求有公共位置的不同回文出现对数，模 $51123987$。

Hint 1

先算全部回文出现数 $P$，所有无序对为 $\binom P2$。

Hint 2

相交不易直接累计，改减去不相交对：左回文终点严格小于右回文起点。

Hint 3

中心 $i$、奇半径 $d$ 的所有起点形成连续区间 `[i-d+1,i]`，所有终点形成 `[i,i+d-1]`；偶回文 `d2[i]=d` 的起点区间为 `[i-d,i-1]`，终点区间为 `[i,i+d-1]`。

Hint 4

对起点数和终点数分别做区间加差分。扫描位置 `i` 时，用 `start[i] * 已有end前缀` 统计右回文从 `i` 开始的不相交对。

Observations

1. 一个半径 $d$ 代表 $d$ 个回文，它们的起点/终点不是散点，而是连续区间，可以差分加入。
2. 两个回文只有“相交”或“严格左—右不相交”两类；补集比直接枚举交叠长度简单。
3. 不相交对按右回文的起点唯一计数，不会像“枚举分割线”那样按间隔长度重复。

Editorial 与正确性

先求 d1,d2，并令 $P=\sum d1+\sum d2$。对每个中心，把它代表的所有回文起点区间加入 start_diff，终点区间加入 end_diff。前缀和后得到 start[i] 与 end[i]。

扫描 $i$ 时，ended_before 是终点小于 $i$ 的回文数，start[i]*ended_before 恰统计所有以 $i$ 开始的右回文与在它之前结束的左回文。每个不相交无序对有唯一右回文，故恰计一次。答案是 $\binom P2-disjoint$。

半径与差分均线性，时间 $O(n)$，空间 $O(n)$。$P$ 可达 $O(n^2)$，使用 long long；组合数先给一个因子除 2 再取模，避免 $P(P-1)$ 溢出。

核心伪代码与参考实现附件

d1, d2 = Manacher(s)
P = sum(d1) + sum(d2)
for each center and radius:
    range_add all represented start positions
    range_add all represented end positions
start, end = prefix_sums(the two difference arrays)
disjoint = sum(start[i] * number_of_palindromes_ending_before_i)
output choose(P, 2) - disjoint  (mod MOD)

完整 GNU C++17 参考实现见附件：CodeForces-17E.cpp

复盘与变式

若题目问相交回文对的交集长度总和，简单补集计数不再够用，需要额外按端点累计权值。若只问回文总数，直接求半径和即可，不必构造差分数组。

高阶扩展：ukuku——从半径数组反造字符串

来源信息、题意与范围

• VJudge：AtCoder-qupc2018_h ukuku
• 原来源：九州大学程序设计竞赛 2018 H
• 大致难度：高阶构造；主要考点：Manacher 半径的逆问题、镜像相等约束、区间并查集

给出 $N\le2\times10^5$ 与数组 $A$。构造一个小写字符串 $S$，使以第 $i$ 个字符为中心的最长奇回文长度恰为 $A_i$。输入保证至少存在一个答案。

Hint 1：恰为 A_i 分成哪两类约束

令 $r_i=(A_i-1)/2$。对 $1\le d\le r_i$ 必须有 $S_{i-d}=S_{i+d}$；若两侧仍在串内，则第 $r_i+1$ 层必须不等。

Hint 2：为什么逐对合并会超时

串全相等时 $\sum r_i=\Theta(N^2)$。一次回文约束其实是“左区间正序 = 右区间逆序”，应批量合并两个有方向的区间对象。

Hint 3：怎样把区间相等下传到字符

为每个 $2^k$ 长度区间建立正向、反向两个节点。合并两个同长度序列；从大层向小层，把一个等价类的前半与前半、后半与后半继续合并，最终落到单字符。

Observations

1. 正向 Manacher 由字符串求半径；逆问题中半径直接产生等式与不等式，目标对象应从“中心扩展过程”换成“字符等价类”。
2. 只合并每个回文最外层字符不够，例如半径 3 同时要求三对字符相等；真正删掉二次工作量的是幂长区间复用。
3. 所有等式合并完后，每个等价类取一个字符；“最长恰好”只剩等价类之间的不等边，按最早出现顺序贪心染最小可用字母即可。存在性保证不会用尽 26 色。

Editorial 与正确性证明

每个中心 $i$ 给出长度 $r_i$ 的序列等式

$$

S[i-r_i\ldots i-1]

\operatorname{reverse}(S[i+1\ldots i+r_i]). $$

把长度按二进制拆成 $O(\log N)$ 个块。第 $k$ 层节点表示某个长度 $2^k$ 的正向或反向序列；同层并查集合并表示两段逐位相等。全部约束加入后从高层向低层传播：正向块的孩子是左正向、右正向；反向块的孩子顺序是右反向、左反向。归纳可知，第 0 层两个位置同属一类，当且仅当它们被全部回文内部等式强制相等。

对每个中心，若 $i-r_i-1$ 与 $i+r_i+1$ 均存在，就在它们的第 0 层等价类间加不等边。给类染色后，同半径内的镜像字符因并查集合并而相等，所以长度至少为 $A_i$；边界两字符因不等边异色，所以不能再扩一层，最长长度恰为 $A_i$。每个回文加入 $O(\log N)$ 次合并，分层节点总数 $O(N\log N)$，总时间与空间均为 $O(N\log N)$。

核心伪代码、实现边界与附件

for every power k:
    make DSU nodes for every length-2^k interval in forward/reverse direction
for center i:
    decompose its left half and reversed right half into equal power blocks
    union corresponding directed blocks
for k from high to 1:
    for each node equal to another node:
        union their first children and union their second children at k-1
for center i with two outside characters present:
    add inequality(class(left_outside), class(right_outside))
greedily color character classes with letters a..z

半径只含奇数；中心和区间下标必须统一为 0 基。第 0 层的正反节点表示同一字符，初始化时就应合并。完整 GNU C++17 附件：AtCoder-qupc2018_h.cpp

复盘与变式

识别信号是“大量区间逐位相等，且一侧可能反向”。若输入不保证有解，需要额外检查：等式类内部不能出现不等边，染色不能超过字母表，并在输出后重新跑一次 Manacher 作最终验证。偶回文也可用同一结构，只需把两半的边界定义改到字符缝隙。

扩展与联系

• Manacher 擅长静态单串全部中心；动态修改或两串回文比较通常需要哈希、线段树或回文树等工具。
• 回文树（palindromic tree/Eertree）按不同回文串建节点，适合统计种类和在线追加；Manacher 记录的是每个中心的出现半径，两者状态含义不同。
• 半径转区间加是常见迁移：当每个中心贡献一串连续端点时，不要逐个枚举半径。

总结与自检

1. d1[i]、d2[i] 的端点和长度公式分别是什么？
2. 镜像初始化为什么要与右边界剩余长度取最小？
3. Manacher 的线性复杂度怎样向右边界记账？
4. Palisection 为什么不能枚举分割线统计不相交对？
5. 怎样从一个半径用两次区间加贡献全部起点与终点？

课后训练建议

先用朴素中心扩展与 d1/d2 对拍长度 30 的随机串。Palindrome 应独立实现；Palisection 即使不提交，也要手算 babb 的半径、起点数、终点数与不相交对，确认补集公式每对只计一次。