第 72 章 回文¶
配套例题：BISHI94 【模板】马拉车算法、BISHI20 回文日期 前置：70-字符串处理、36-哈希与字符串哈希、71-字符串匹配KMP
回文串：从左往右读和从右往左读完全相同的串。
回文问题在竞赛里有一个非常清晰的「三层解法阶梯」：
| 需求 | 解法 | 复杂度 |
|---|---|---|
| 判一个串是不是回文 | s == s[::-1] |
\(O(n)\)，C 层 |
| 找最长回文子串（\(n \le 3000\)） | 中心扩展 | \(O(n^2)\) |
| 找最长回文子串（\(n \le 10^6\)） | Manacher | \(O(n)\) |
| \(O(1)\) 判任意子串 \(s[l:r]\) 是否回文 | 正反哈希 或 Manacher 的 \(p\) 数组 | 预处理 \(O(n)\)，查询 \(O(1)\) |
这一章把这四层都讲透。
72.1 回文判定¶
不要手写双指针：
# ❌ 慢 10 倍以上（Python 层循环）
def is_pal_slow(s):
i, j = 0, len(s) - 1 # 两端各一个游标，向中间靠拢
while i < j: # i == j（正中间那个字符）不必比，它和自己天然相等
if s[i] != s[j]:
return False
i += 1
j -= 1
return True
唯一值得手写的场景：需要提前退出且串很长又几乎必然在前几位失配——
但 s[::-1] 的 \(O(n)\) 复制在 C 层跑，\(n \le 10^6\) 都无所谓。
变体¶
| 需求 | 写法 |
|---|---|
| 忽略大小写 | t = s.lower(); t == t[::-1] |
| 只看字母数字 | t = "".join(c for c in s.lower() if c.isalnum()) |
| 数字是否回文 | str(x) == str(x)[::-1] |
bytes 也一样 |
b == b[::-1] |
72.2 中心扩展¶
每个回文串都有一个中心。 枚举中心，向两边扩展到不能再扩。
坑：回文有奇偶两种——奇长度的中心是一个字符，偶长度的中心是两个字符之间的缝。 所以要枚举 \(2n-1\) 个中心。
def longest_palindrome_expand(s):
"""中心扩展求最长回文子串，返回 (起点, 长度)。O(n^2)。"""
n = len(s)
if n == 0:
return 0, 0
best_l, best_len = 0, 1 # 非空串至少有长度 1 的回文（单个字符）
for c in range(n):
for d in (0, 1): # d=0 奇数长度，d=1 偶数长度
l, r = c, c + d # d=1 时中心是 c 与 c+1 之间那道缝
while l >= 0 and r < n and s[l] == s[r]:
l -= 1 # 两端同时外扩，扩不动就退出
r += 1
# 退出时 l、r 各多走了一步：真正的回文是 s[l+1..r-1]，长度 (r-1)-(l+1)+1 = r-l-1
if r - l - 1 > best_len:
best_len = r - l - 1
best_l = l + 1
return best_l, best_len
| 优点 | 缺点 |
|---|---|
| 代码短、不用想 | \(O(n^2)\)：\(n = 3000\) 时 Python 里已经要几秒 |
| 顺手能统计「回文子串个数」 | \(n \ge 10^5\) 完全不可用 |
统计回文子串总数：每次扩展成功一次就是一个新的回文子串， 所以把
while的成功次数累加起来就是答案（\(O(n^2)\)）。 \(O(n)\) 的做法要用 回文自动机（PAM，Palindromic Automaton） 或 Manacher + 差分。
72.3 Manacher（马拉车）¶
Manacher 算法得名于提出者 Glenn Manacher，中文按发音习惯叫「马拉车」。 它一次 \(O(n)\) 扫描求出以每个位置为中心的最长回文半径， 「最长回文子串」只是顺手在这张表上取个最大值。
第一步：奇偶统一¶
在每两个字符之间以及首尾插入分隔符 #：
原串长 \(n\) → 新串长 \(2n+1\)，每个回文（不论奇偶）在新串里都是奇长度。
而且插入 # 有一个非常漂亮的性质：
新串中位置 \(i\) 的回文半径 \(p[i]\)（不含中心）， 恰好等于原串中对应回文子串的长度。
所以答案就是 \(\max p[i]\)，奇偶完全不用分类讨论。
第二步：镜像预测¶
维护当前最靠右的回文区间 \([c-p[c],\ c+p[c]]\)（中心 \(c\)，右端 \(r\)）。 若当前中心 \(i < r\)，设它关于 \(c\) 的镜像是 \(\text{mir} = 2c-i\)，则
为什么要和 \(r-i\) 取 \(\min\)：镜像的回文只有在 \([c-p[c], r]\) 这个已知区间内才可靠，
超出部分完全没有信息，必须重新暴力扩展。忘了这个 min 是 Manacher 最常见的错。
模板¶
def manacher(s):
"""返回变换串上的回文半径数组 p（长度 2n+3，下标 1..2n+1 有效）。
- max(p) 就是原串最长回文子串的长度；
- 原串子串 s[l:r] 是回文 <=> p[l + r + 1] >= r - l。
s 传 bytes 更快（比较的是 int）。整体 O(n)。
"""
if isinstance(s, str):
s = s.encode() # 统一成 bytes：索引出来是 int，比较更快
n = len(s)
m = 2 * n + 1 # 插满 '#' 后的长度：n 个原字符 + n+1 个 '#'
# t = ^ # s0 # s1 # ... # $，两端哨兵保证扩展循环自然停止，省掉越界判断
t = bytearray(b'^' + b'#' * m + b'$')
# ★ 切片步长赋值，C 层一次拷贝：'^' 占 0 号位，原字符落在 2, 4, 6, ...
t[2:2 + 2 * n:2] = s
p = [0] * (m + 2) # p[i] = 变换串上以 i 为中心的回文半径（不含中心）
c = r = 0 # 最右回文区间的中心与右端
for i in range(1, m + 1): # 只扫有效区间，两端哨兵不当中心
if i < r: # i 落在已知区间内，可以借镜像的结论当下界
mir = 2 * c - i # i 关于中心 c 的镜像位置
k = r - i # 已知区间在 i 右侧还剩这么多字符可信
pm = p[mir]
if pm < k: # k = min(p[mir], r - i)
k = pm # 镜像半径伸出已知区间的部分不可信，得截断
else:
k = 0 # i 在已知区间之外，没有任何可借的信息
while t[i - k - 1] == t[i + k + 1]: # 哨兵 ^ / $ 保证一定失配停下
k += 1 # 从下界继续逐位暴力扩
p[i] = k
if i + k > r:
c, r = i, i + k # 右端更靠右了，中心必须和 r 一起换
return p
def longest_palindrome_len(s):
"""最长回文子串的长度，O(n)。"""
return max(manacher(s))
def make_palindrome_checker(s):
"""返回一个 O(1) 判定 s[l:r]（左闭右开）是否回文的函数。预处理 O(n)。"""
p = manacher(s)
def is_pal(l, r):
# s[l:r] 长 r-l，插 '#' 之后它在变换串里的半径也恰好是 r-l；
# 中心下标 l+r+1 的推导见下方正文
return p[l + r + 1] >= r - l # 中心在变换串的 l+r+1 处
return is_pal
「中心是 \(l+r+1\)」怎么来的：原串 \(s[l]\) 落在 \(t\) 的下标 \(2l+2\)， \(s[r-1]\) 落在 \(2(r-1)+2 = 2r\)，中点就是 \(\frac{(2l+2)+2r}{2} = l+r+1\)。
三个实现细节¶
| 细节 | 作用 |
|---|---|
t = b'^' + b'#'*m + b'$' 两端不同的哨兵 |
扩展循环一定会失配停下，省掉两次越界判断 |
t[2:2+2n:2] = s（切片步长赋值） |
比 b'#'.join(...) 快好几倍（见 70.2） |
全程 bytearray / int 比较 |
比 str 快约 2 倍 |
本机实测（CPython 3.9，\(n = 10^6\)）：
| 数据 | 耗时 |
|---|---|
| 随机 26 字母串 | 0.37 s |
abab…ab |
0.54 s |
全 a（最坏结构） |
0.53 s |
为什么 Manacher 是 \(O(n)\)：内层
while每成功一次，\(r\) 就至少增大 1， 而 \(r\) 单调不减且 \(\le 2n+1\)。所以所有while的总执行次数是 \(O(n)\)。 这和 Z 函数（71.6）、单调栈的均摊论证是同一套。
72.4 哈希法：\(O(1)\) 判任意子串是否回文¶
思路极简单：正串的哈希 == 反串对应位置的哈希。
# 依赖 36 章的 StringHash 类
def build_palindrome_checker_hash(s, StringHash):
"""返回 O(1) 判定 s[l:r] 是否回文的函数。预处理 O(n)。"""
n = len(s)
fwd = StringHash(s) # 正串的前缀哈希
rev = StringHash(s[::-1], base=fwd.base) # ★ 必须用同一个 base 和模数
def is_pal(l, r):
# 反串是整体翻转，正串下标 j 对应反串下标 n-1-j，
# 所以区间 [l, r) 翻过去就是 [n-r, n-l)；两段哈希相等即回文
return fwd.get(l, r) == rev.get(n - r, n - l)
return is_pal
⚠️ 正串和反串必须用同一个
base和同一个模数，否则完全没有可比性。base=fwd.base那一行是全部关键。见 36-哈希与字符串哈希。
Manacher vs 哈希：怎么选¶
| Manacher | 正反哈希 | |
|---|---|---|
| 预处理 | \(O(n)\) | \(O(n)\) |
| 判 \(s[l:r]\) 是否回文 | \(O(1)\) | \(O(1)\) |
| 求最长回文子串 | ✅ 直接 max(p) |
⚠️ 要二分半径，\(O(n\log n)\) |
| 求以每个位置为中心的最长回文 | ✅ 就是 \(p\) 数组 | ⚠️ 每个都要二分 |
| 冲突风险 | ✅ 无 | ⚠️ 有（\(2^{61}-1\) 单模已经足够安全） |
| 能否处理「回文 + 其它子串比较」 | ❌ 只管回文 | ✅ 万能 |
| 代码量 | 中等 | 短（有现成的类） |
| Python 常数 | 快 | 慢（大整数乘法 + 取模） |
决策： - 题目只问回文 → Manacher； - 题目既要判回文又要比较任意子串 → 哈希（一套代码解决两件事）； - 需要「统计本质不同的回文子串个数」 → 回文自动机 PAM（本教程不展开， 可用 Manacher + 哈希 +
set近似替代）。
72.5 常见回文题型¶
| 题型 | 做法 |
|---|---|
| 最长回文子串 | Manacher |
| 最长回文子序列 | 区间 DP（和回文算法无关！见 103 章） |
| 回文子串个数 | Manacher 的 \(p\) 数组：以 \(i\) 为中心的回文个数 \(= \lceil p[i]/2 \rceil\) |
| 把串分成最少几段全是回文 | DP + \(O(1)\) 判回文 |
| 判断某个数/日期是否回文 | 转成 str 再 [::-1]（BISHI20） |
| 最少加几个字符使全串回文 | KMP：在 \(s + \texttt{sep} + s^R\) 上求 \(\pi\)（71 章） |
| 回文串的构造 | 枚举「前一半」，后一半是它的镜像（BISHI20 的核心思路） |
「枚举一半」是回文构造题的通用套路： 长度 \(L\) 的回文由前 \(\lceil L/2 \rceil\) 位唯一确定。 所以要枚举「所有长度为 8 的回文数」，只需枚举前 4 位的 \(9000\) 种可能， 而不是枚举 \(10^8\) 个 8 位数——指数直接减半。
72.6 例题¶
BISHI94 【模板】马拉车算法（中等）¶
给定长度 \(n \le 10^6\) 的小写字母串 \(S\)，求最长回文子串的长度。 题面见 BISHI94 原题（牛客）。 题解见
solutions/BISHI94.py（已用官方样例验证）。
\(n = 10^6\)，中心扩展的 \(O(n^2)\) 是 \(10^{12}\)，必挂。只能 Manacher。
import sys
def main():
s = sys.stdin.buffer.read().split()[0] # split() 顺带去掉 \r\n
n = len(s)
m = 2 * n + 1 # 插满 '#' 后的长度：n 个原字符 + n+1 个 '#'
# t = ^ # s0 # s1 # ... # $，两端哨兵保证扩展循环自然停止
t = bytearray(b'^' + b'#' * m + b'$') # 总长 2n+3
t[2:2 + 2 * n:2] = s # ★ 切片步长赋值，原字符落在偶数下标
p = [0] * (m + 2) # p[i] = 以 i 为中心的回文半径（不含中心）
c = r = 0 # 最右回文区间的中心与右端
best = 0
for i in range(1, m + 1): # 两端哨兵不当中心，只扫有效区间
if i < r: # i 在已知区间内，借镜像位置的结论当下界
mir = 2 * c - i # i 关于中心 c 的镜像位置
k = r - i # 已知区间在 i 右侧还剩这么多字符可信
pm = p[mir]
k = pm if pm < k else k # 下界 = min(镜像半径, 右边界剩余)
else:
k = 0 # 已知区间管不到 i，只能从 0 开始扩
while t[i - k - 1] == t[i + k + 1]: # 哨兵保证一定会失配停下
k += 1 # 从下界继续逐位扩
p[i] = k
if i + k > r:
c, r = i, i + k # 右端更靠右了，中心必须跟着一起换
if k > best:
best = k # 半径 k 就是原串中那段回文的长度
sys.stdout.write("%d\n" % best)
main()
复杂度 \(O(n)\)。本机实测 \(n = 10^6\) 约 0.4–0.55 秒，时限「其他语言 2 秒」，安全。
四个坑：
p[i]的初值必须是 \(\min(r-i,\ p[\text{mir}])\)。 忘了和 \(r-i\) 取 \(\min\)，就会越过已知区间用上不可靠的信息，答案错；- 更新最右区间用
if i + k > r，且要同时更新中心c。 只更新r不更新c会让后面所有的镜像计算全错； - 两端哨兵
^和$必须不同、且不等于#和任何字母。 它们的作用是让while t[i-k-1] == t[i+k+1]在到达边界时自然失配， 省掉两次下标越界检查——在 \(2\times10^6\) 次循环里这是实打实的时间； - 读入必须
split()[0]，直接read()会把换行符带进来，答案偏大。
答案为什么就是
max(p)：变换串中半径为 \(k\) 的回文， 覆盖了 \(k\) 个#和 \(k\) 个原字符……更准确地说，插入#之后， 原串中长度 \(L\) 的回文在 \(t\) 中的半径恰好是 \(L\)。 可以拿aaa手验：\(t = \texttt{\^{}\#a\#a\#a\#\$}\)， 中心在正中间的#上时半径是 3，正是答案 3 ✓
BISHI20 回文日期（简单）¶
8 位数字
YYYYMMDD表示一个日期，若这 8 位数字本身是回文数，则称回文日期。 给定 \(a \le b\)，求 \([a,b]\) 内真实存在的回文日期数量。 题面见 BISHI20 原题（牛客）。 题解见solutions/BISHI20.py（已用官方样例验证）。
这题的考点是「枚举一半」，不是回文算法。
逐日枚举要跑 \(9000 \times 365 \approx 3.3\times10^6\) 天，还要写日期递增逻辑。 但注意：
8 位回文数由前 4 位（年份）唯一确定：后四位必须是年份的逆序， 即 \(\texttt{MM} = y_4y_3\)，\(\texttt{DD} = y_2y_1\)。
年份只有 \(1000 \sim 9999\) 共 9000 个，逐个构造再判合法性即可。
import sys
data = sys.stdin.buffer.read().split()
a, b = int(data[0]), int(data[1])
DAYS = [0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31] # 下标 0 空出来，DAYS[m] 直接按月取
ans = 0
for y in range(1000, 10000): # 8 位回文数由前 4 位唯一确定，只需枚举 9000 个年份
s = str(y)
d = int(s + s[::-1]) # ★ 该年份下唯一可能的回文日期
if d < a or d > b:
continue # 落在询问区间之外
m, day = d // 100 % 100, d % 100 # 后四位拆开：d//100%100 是 MM，d%100 是 DD
if not 1 <= m <= 12: # 构造出来的月份可能是 00、20 这种非法值
continue
lim = DAYS[m] # 该月天数上限
if m == 2 and ((y % 4 == 0 and y % 100 != 0) or y % 400 == 0):
lim = 29 # 闰年 2 月 29 天；只写 y%4==0 会把 1900、2100 算成闰年
if 1 <= day <= lim: # DD 也可能构造成 00，所以下界同样要判
ans += 1
print(ans)
复杂度 \(O(9000)\)，瞬间出结果。
四个坑：
- 构造出的月份可能非法：
y = 2000→20000002，月份是00；y = 2002→20022002，月份是20。必须判 \(1 \le m \le 12\)； - 闰年规则要写全：「能被 4 整除但不能被 100 整除，或能被 400 整除」。
只写
y % 4 == 0会把 1900、2100 算成闰年； - 日期也可能是
00：y = 1000→10000001，DD = 01合法； 但y = 2010→20100102合法，而y = 2000的DD = 02配上非法月份被挡掉了。 月份和日期都要判； - 题面说明里的「20010002」是笔误，真正的回文日期是
20011002（2001-10-02）。 遇到题面文字和「真实存在的日期」冲突时，以逻辑和样例的最终答案为准—— 样例 2 的答案是 2，正好对应20011002和20100102。
本题给出的判据：所有「在一个大区间里数满足某种对称结构的数」的题， 第一反应都应该是枚举决定性的那一半，而不是枚举整个区间。 同类：回文数计数、\(\text{ABCCBA}\) 型车牌、镜像对称的数位 DP。 见 85-基础数学与递推 的数位处理。
72.7 本章速查¶
| 要点 | 结论 |
|---|---|
| 判一个串是否回文 | s == s[::-1]，C 层 \(O(n)\)，别手写双指针 |
| 中心要枚举几个 | \(2n-1\) 个（奇 \(n\) 个 + 偶 \(n-1\) 个） |
| 中心扩展 | \(O(n^2)\)，\(n \le 3000\) 可用 |
| \(n \ge 10^5\) 求最长回文 | Manacher，\(O(n)\) |
| Manacher 的插入符 | 首尾和每两字符之间插 #，新串长 \(2n+1\) |
插 # 的妙处 |
新串的半径 \(p[i]\) = 原串回文的长度，奇偶不用分类 |
| 半径初值 | \(\min(p[\text{mir}],\ r-i)\)——忘了 min 就错 |
| 更新最右区间 | if i+k > r: c, r = i, i+k——c 必须一起更新 |
| 两端哨兵 | 用 ^ 和 $（互不相同），省掉越界判断 |
| 构造变换串 | bytearray + t[2::2] = s（切片步长赋值） |
| 复杂度证明 | \(r\) 单调不减且 \(\le 2n+1\)，while 总量 \(O(n)\) |
| 实测速度 | \(n = 10^6\) 约 0.4–0.55 s |
| \(O(1)\) 判 \(s[l:r]\) 回文（Manacher） | p[l+r+1] >= r-l |
| \(O(1)\) 判 \(s[l:r]\) 回文（哈希） | 正串哈希 == 反串对应区间哈希，base 必须相同 |
| 只问回文 → | Manacher |
| 还要比较任意子串 → | 哈希 |
| 最长回文子序列 | 区间 DP，和本章算法无关 |
| 回文构造 / 计数 | 枚举前一半，后一半是镜像 |
| 最少补几个字符成回文 | KMP：在 \(s + \texttt{sep} + s^R\) 上求 \(\pi\) |
| 看到什么 → 想到什么 |
|---|
| 「最长回文子串」+ \(n\) 很大 |
| 「每个位置为中心的最长回文」 |
| 「回文子串个数」 |
| 「多次询问某子串是否回文」 |
| 「分成最少几段回文」 |
| 「回文子序列」 |
| 「区间里有多少回文数/日期」 |