# 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](https://vjudge.net/problem/POJ-3974) - 原来源：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)$。 ### 核心伪代码与参考实现附件 ```text 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](../../参考实现/04-KMP与Manacher/POJ-3974.cpp) ### 复盘与变式 `HDU-3068 最长回文` 是同模型题，可用于独立复写。若要求输出一个最长回文的位置，记录产生最大长度的中心，再用半径公式还原左右端点。 ## 灵活性实验室：Palisection ### 来源信息与题意 - VJudge：[CodeForces-17E Palisection](https://vjudge.net/problem/CodeForces-17E) - 原题：[Codeforces Beta Round 17](https://codeforces.com/problemset/problem/17/E) - 难度：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)$ 溢出。 ### 核心伪代码与参考实现附件 ```text 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](../../参考实现/04-KMP与Manacher/CodeForces-17E.cpp) ### 复盘与变式 若题目问相交回文对的交集长度总和，简单补集计数不再够用，需要额外按端点累计权值。若只问回文总数，直接求半径和即可，不必构造差分数组。 ## 高阶扩展：ukuku——从半径数组反造字符串 ### 来源信息、题意与范围 - VJudge：[AtCoder-qupc2018_h ukuku](https://vjudge.net/problem/AtCoder-qupc2018_h) - 原来源：九州大学程序设计竞赛 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)$。 ### 核心伪代码、实现边界与附件 ```text 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](../../参考实现/04-KMP与Manacher/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` 的半径、起点数、终点数与不相交对，确认补集公式每对只计一次。