回文与回文半径 | Codeboy's Blog

abacdcabba 中，aba、cdc 和 abba 都能从两头读到同样的字符。程序若只问“最长的一段”，答案却是跨过前两块边界的 bacdcab。同一段文本上的最长回文、回文出现次数、不同回文数和最少回文分块，是四种不同输出。先约定位置和计数对象，后面的线性算法才有准确含义。

形式陈述

反转不变与连续区间

设词 $s$ 长度为 $n$ ，位置从零开始。反转词 $s^R$ 的第 $i$ 位为 $s[n-1-i]$ 。若 $s=s^R$ ，称 $s$ 为回文。等价地，对每个 $0\le i<n$ ，都有 $s[i]=s[n-1-i]$ 。单字符与空词都是回文；下文计数与分块只计非空回文，空词留作边界对象。

回文子串的一次出现是半开区间 $[l,r)$ ，满足 $0\le l<r\le n$ 且 $s[l:r]$ 回文。两个区间可以重叠，也可以装着相同内容。aaa 有六次非空回文出现：三个 a、两个 aa、一个 aaa；不同内容只有三种。

奇中心与偶中心

奇数长度的回文以一个字符为中心。定义

\operatorname{odd}[i]=\max\{k\ge1:s[i-k+1:i+k]\text{ 回文且区间合法}\}.

它包含中心字符，所以 a 的半径是一，对应长度 $2k-1$ 。例如 aba 在字符 b 上半径为二，对应区间 $[0,3)$ 。

偶数长度的回文以一个字符间隙为中心。令位置 $i$ 表示字符 $i$ 之前的间隙，定义

\operatorname{even}[i]=\max\{k\ge0:s[i-k:i+k]\text{ 回文且区间合法}\},\qquad0\le i<n.

它对应长度 $2k$ 。abba 的中心在两个 b 之间，即 $i=2$ ，半径二。半径零只表示这个间隙没有非空偶回文。文本最后的间隙 $i=n$ 也只能有零半径，因此不存这一项；最前间隙 $i=0$ 保留为零，使两数组都长 $n$ 。空输入返回两个空数组。

直觉

每个中心只保存最外一圈

如果一段回文两端各删一个字符，剩下仍是回文。因此某个奇中心的最大半径为 $k$ 时，半径 $1,\ldots,k$ 全部成立；偶中心则是 $1,\ldots,k$ 。半径超过 $k$ 的下一圈要么越界，要么两端不相等。一个整数就完整描述了这个中心上的所有出现。

每个非空区间恰有一个中心和一种奇偶性，故非空回文出现总数为

N_{\rm occ}=\sum_{i=0}^{n-1}\operatorname{odd}[i]+ \sum_{i=0}^{n-1}\operatorname{even}[i].

这里没有去重，也没有重复计入同一区间。内容相同而位置不同的两段仍是两次出现。对 $a^n$ ，所有非空子串都是回文，故总数为 $n(n+1)/2$ ；两个长度为 $n$ 的数组仍能装下这些信息。线性表示不等于线性时间列出全部二次方个答案。[1]

最大与最长也须分开

“在这个中心最大”指不能沿同一中心继续扩张；“全文最长”还要和其他中心比较。abacdcabba 里单字符 d、cdc、acdca 都不是各自中心的最大回文，因为都可沿中心四扩为 bacdcab。但它们仍是合法回文，后续最少分块可能需要其中的 cdc，不能只保留一份最大区间列表就丢掉较短半径。

Manacher 算法在线性时间计算这里定义的两份最大半径数组。它不显式输出每个较短区间；这些区间通过半径仍可恢复。若接口承诺输出字符串副本，还须把复制字符的成本加上，不能只按区间数量计时。

例子与边界

十个字符上的四种答案

对 s = abacdcabba：

$i$	0	1	2	3	4	5	6	7	8	9
字符	a	b	a	c	d	c	a	b	b	a
odd	1	2	1	1	4	1	1	1	1	1
even	0	0	0	0	0	0	0	0	2	0

奇半径和为十四，偶半径和为二，总共十六次出现。最长回文为 $[1,8)$ 的 bacdcab，长度七。不同内容共有十种：a,b,c,d,bb,aba,cdc,abba,acdca,bacdcab。aba|cdc|abba 是三块回文分解；它的最优性还需比较全部合法切点，不能从半径表一眼断言。

子串不是子序列，字符也不是印刷字形

abca 中选位置 $0,1,3$ 得到回文子序列 aba，但它不是连续子串。本单元所有区间、半径和分块都要求连续，不能拿最长回文子序列的动态规划替代。

相等比较必须先固定符号粒度。Python 字符串下标按 Unicode 码点；带组合音标的一个可见字形可能含多个码点。大小写忽略、去标点、Unicode 规范化都是额外的输入处理规则。算法不会自行把不同码点当相等；若预处理改了长度，还要保存映回原文的位置映射。

推论与应用

常数时间核验一个区间

已知两个数组，要判断 $[l,r)$ 是否回文，先检查 $0\le l\le r\le n$ 。空区间返回真。令 $m=r-l>0$ 、 $c=\lfloor(l+r)/2\rfloor$ ：

$m$ 为奇数时，检查 $\operatorname{odd}[c]\ge(m+1)/2$
$m$ 为偶数时，检查 $\operatorname{even}[c]\ge m/2$

例如 $[3,6)$ 是 cdc，中心四、所需半径二，而 odd[4]=4，因此通过。 $[6,10)$ 是 abba，偶中心八、所需半径二，也通过。 $[2,8)$ 需要 even[5]≥3，实际为零，立即拒绝。这里预处理可以线性完成，单个区间查询只查一个整数。

最长回文长度是所有 $2\operatorname{odd}[i]-1$ 与 $2\operatorname{even}[i]$ 的最大值；空串约定结果长零、区间 $[0,0)$ 。若有多个最长区间，应另外约定返回最左、全部或任意一个，不能让实现的循环顺序偷偷决定公共接口。

换一种摘要，会得到另一种工具

回文树为每种不同回文内容建一个节点，并借后缀链接累计出现次数。它回答的是按内容聚合的问题，与按中心组织的半径数组互补。最少回文分解再把区间判断作为转移条件，输出覆盖全文的最少块数及真实切点。

手算迁移用 aaaa：奇半径为 $[1,2,2,1]$ ，偶半径为 $[0,1,2,1]$ ，出现总数十、不同内容四、最长长度四、最少分块一。能把这四个数同时解释清楚，才算没有混淆本页的输出对象。

参考资料

[1] Gabriele Fici, Travis Gagie, Juha Kärkkäinen and Dominik Kempa, A Subquadratic Algorithm for Minimum Palindromic Factorization, arXiv:1403.2431v2, 2014，§1–2：最大中心回文对全部出现的压缩表示，以及分块问题的区别。
Mikhail Rubinchik and Arseny M. Shur, EERTREE: An Efficient Data Structure for Processing Palindromes in Strings, arXiv:1506.04862v2, 2015，Definitions and Notation、§2.1。该文采用一基下标；本文统一为零基半开区间，奇半径计入中心字符。

形式陈述 ​

反转不变与连续区间 ​

奇中心与偶中心 ​

每个中心只保存最外一圈 ​

最大与最长也须分开 ​

十个字符上的四种答案 ​

子串不是子序列，字符也不是印刷字形 ​

常数时间核验一个区间 ​

换一种摘要，会得到另一种工具 ​

反向链接