第 71 章 字符串匹配与 KMP¶
配套例题：BISHI92 【模板】前缀函数（KMP） 来源：S4
模板.docxKMP 段 前置：70-字符串处理、36-哈希与字符串哈希
KMP（Knuth-Morris-Pratt，取三位作者 Knuth、Morris、Pratt 的姓氏首字母）
是最经典的字符串匹配算法。它真正的产物是一张前缀函数表——
在各家资料里也叫 next 数组或 fail 数组，本章统一记作 \(\pi\)。
这一章有一个反直觉的核心结论，先说在前面：
在 Python 里，纯粹的「找子串」几乎永远应该用
str.find/in， 手写 KMP 只会更慢（实测慢 10–240 倍）。但 KMP 的前缀函数（
next数组）本身是不可替代的—— 求 border、求最小循环节、求所有周期，这些是find做不到的。
所以学 KMP 的正确姿势是：学前缀函数，而不是学「怎么找子串」。
71.1 暴力匹配¶
在文本 \(t\)（长 \(n\)）里找模式 \(p\)（长 \(m\)）：
def naive_search(t, p):
"""暴力匹配，最坏 O(nm)。"""
n, m = len(t), len(p)
res = []
for i in range(n - m + 1): # i 是对齐起点；再往后 p 就放不下了
j = 0 # j = 本轮已经比对成功的长度
while j < m and t[i + j] == p[j]:
j += 1
if j == m: # 一路比到底，说明 p 出现在下标 i
res.append(i)
# 失配后 i 只 +1、j 归零：刚刚比对成功的 j 个字符全白比了
return res
最坏情况：\(t = \texttt{aaaa}\cdots\texttt{a}\)，\(p = \texttt{aaa}\cdots\texttt{ab}\)。 每个起点都要比到最后一位才失配，\(O(nm)\)。\(n = m = 10^5\) 时是 \(10^{10}\)，必挂。
暴力的浪费在哪：失配后 \(i\) 只前进 1 位，已经比对成功的信息全丢了。 KMP 的全部思想就是：利用「模式串自己和自己的匹配关系」， 让失配后不必从头再来。
71.2 前缀函数（next 数组）¶
定义¶
对字符串 \(s\)（下标从 0 开始），
即：\(s\) 的前缀 \(s[0..i]\) 中，最长的「既是真前缀又是真后缀」的长度。
「既是真前缀又是真后缀」的串叫 border（边界）。\(\pi[i]\) 就是最长 border 的长度。
逐个验证：
| \(i\) | 前缀 \(s[0..i]\) | 最长 border | \(\pi[i]\) |
|---|---|---|---|
| 0 | a |
空（真前缀不能是整串） | 0 |
| 1 | aa |
a |
1 |
| 2 | aab |
空 | 0 |
| 3 | aaba |
a |
1 |
| 6 | aababaa |
aa |
2 |
| 7 | aabaabab… → aabab aa b |
aab |
3 |
递推：失配链¶
关键引理：\(\pi[i]\) 的候选值只能来自这条链
为什么：\(s[0..i]\) 的 border 去掉最后一个字符，就是 \(s[0..i-1]\) 的 border。 而 \(s[0..i-1]\) 的所有 border 恰好就是 \(\pi[i-1]\) 沿着这条链一路跳下去得到的集合。
于是算法是：用一个游标 \(k\) 记住「当前候选 border 长度」，
- 若 \(s[k] = s[i]\)，则 \(\pi[i] = k+1\)；
- 否则沿链回退 \(k \leftarrow \pi[k-1]\)，直到匹配上或 \(k = 0\)。
def prefix_function(s):
"""前缀函数（KMP 的 next 数组）。pi[i] = s[0..i] 的最长 border 长度。
均摊 O(n)：k 每轮最多 +1，所以总的回退量不超过总的增加量。
s 可以是 str 或 bytes（bytes 更快，比较的是 int）。
"""
n = len(s)
pi = [0] * n
k = 0 # 当前候选 border 长度，同时也是「下一个要比的下标」
for i in range(1, n): # pi[0] 恒为 0（真前缀不能是整串），所以从 1 起
c = s[i] # 取进局部变量，内层 while 每轮少一次索引
while k and s[k] != c: # 长度 k 的候选接不上 c，换一个更短的候选
k = pi[k - 1] # ★ 跳到 pi[k-1]：s[0..k-1] 的最长 border
if s[k] == c: # 接上了，候选前缀整体加长一位
k += 1
pi[i] = k # k == 0 表示 s[0..i] 没有非空 border
return pi
k = pi[k-1] 为什么不是 k = 0：长度 \(k\) 的候选接不上 \(s[i]\)，
但比 \(k\) 短的候选未必接不上，直接归零就把它们全丢了，等于退回暴力。
而 \(s[0..i-1]\) 的全部 border 恰好构成
\(k,\ \pi[k-1],\ \pi[\pi[k-1]-1],\ \dots,\ 0\) 这条严格递减的链，
所以「换成次长的候选」就是沿链走一步——pi[k-1] 正是长度 \(k\) 的那个前缀自己的最长 border。
链一定会终止：每跳一次 \(k\) 至少减 1，跳到 0 就只能重新开始。
复杂度是 \(O(n)\)（均摊）：内层 while 每执行一次 \(k\) 至少减 1，
而 \(k\) 在整个循环里总共只增加了不超过 \(n\) 次，所以回退总量 \(\le n\)。
和单调栈的均摊论证是同一类（37-单调栈与单调队列）。
两种下标约定：本教程用
pi[i]表示「以 \(i\) 结尾的前缀」的 border 长度（0-indexed）。 S4模板.docx里的 C++ 写法用f[i+1] = ...（1-indexed 的next数组）， 两者只差一个平移：f[i+1] == pi[i]。混用会导致差一错误，选一种就别换。
71.3 KMP 匹配¶
有了模式串 \(p\) 的 \(\pi\) 数组，在文本 \(t\) 上扫描时用同样的失配链回退：
def kmp_search(t, p):
"""在 t 中找出 p 的所有出现位置（可重叠），返回起始下标列表。O(n + m)。"""
m = len(p)
if m == 0:
return list(range(len(t) + 1)) # 空串在每个位置（含末尾）都算出现一次
pi = prefix_function(p) # 只对模式串预处理，与文本无关
res = []
k = 0 # 当前已匹配的长度，同时是 p 中下一个要比的下标
for i in range(len(t)):
c = t[i]
while k and p[k] != c: # 与构建循环同形，只是把 s[k] 换成了 p[k]
k = pi[k - 1] # ★ 同一条失配链：换成次长的「已匹配前缀」
if p[k] == c:
k += 1
if k == m: # 已匹配长度到达 m，完整命中一次
res.append(i - m + 1) # 命中的末位是 i，起点就是 i-m+1
k = pi[k - 1] # ★ 回退，允许重叠匹配
return res
两段循环是同一个模板。逐行对照 prefix_function，差别只有三处：
| 构建 \(\pi\) | 匹配 | |
|---|---|---|
| 游标 \(k\) 的含义 | 候选 border 的长度 | 已匹配的前缀长度 |
| 拿谁和谁比 | s[k] 对 s[i]（串和自己比） |
p[k] 对 t[i]（模式对文本） |
| 命中之后 | 只记 pi[i] = k |
多一句「记录位置并回退」 |
回退用的是同一句 k = pi[k-1]，因为两处问的是同一个问题：
「已经匹配上的这 \(k\) 个字符里，最长的那个『既是前缀又是后缀』有多长」。
k = pi[k-1]这一行决定了「是否允许重叠」： - 写k = pi[k-1]→ 允许重叠（"aaa"中找"aa"得到 2 个）； - 写k = 0→ 不允许重叠（得到 1 个，和str.count一致）。
另一种写法：拼接法¶
把 \(\pi\) 函数直接用在拼接串上，代码更短：
def kmp_search_concat(t, p, sep=b"\x00"):
"""在 s = p + sep + t 上求前缀函数，pi 值等于 |p| 的位置就是一次匹配。
sep 必须是 p 和 t 中都不出现的字符，保证 border 不会跨过分隔符。
代价：多用 O(n + m) 的内存。
"""
m = len(p)
s = p + sep + t # p 占下标 0..m-1，sep 占 m，t 从 m+1 开始
pi = prefix_function(s)
# pi[i] == m 表示以 i 结尾、长度 m 的那一段等于 p；该段起点是 i-m+1，
# 减去 t 的偏移 m+1，在 t 中的下标就是 i-2m
# 下界取 2m：t 的第 0 位若就是一次匹配，它结束在 i = 2m（写成 2m+1 会漏掉这一处）
return [i - 2 * m for i in range(2 * m, len(s)) if pi[i] == m]
分隔符不能省。不加分隔符时，
p = "aa"、t = "aaa"会让 \(\pi\) 值超过 \(m\)， 匹配位置就全错了。这是拼接法唯一的坑。
71.4 现实：str.find 是 C 实现，几乎总是更快¶
CPython 的 str.find / bytes.find / in 用的是
Crochemore-Perrin（two-way）算法加上一个坏字符跳表——
\(O(n+m)\) 最坏复杂度，而且整个循环在 C 层。
本机实测（CPython 3.9，\(n = 10^6\)）：
| 数据 | str.find 找全部出现 |
手写 KMP | 倍数 |
|---|---|---|---|
随机 ab 串，$ |
p | = 20$ | 0.0071 s |
| \(t = \texttt{a}^{10^6}\)，\(p = \texttt{a}^{1000}\texttt{b}\)（暴力最坏） | 0.0004 s | 0.1046 s | 慢 241 倍 |
str.find 只找第一次出现 |
0.00022 s | — | — |
结论表：
| 需求 | 用什么 |
|---|---|
| 判子串是否存在 | p in t |
| 找第一次出现的位置 | t.find(p) |
| 数不重叠出现次数 | t.count(p) |
| 找所有出现位置（可重叠） | while (i := t.find(p, i)) >= 0 循环，仍比 KMP 快 |
| 求 border / 最小循环节 / 所有周期 | 必须 KMP 的 \(\pi\) 数组 |
| 求每个前缀的最长 border（BISHI92） | 必须 \(\pi\) 数组 |
| 求最长公共前缀（LCP）数组 | Z 函数或后缀数组 |
| 需要 \(O(1)\) 比较任意两个子串 | 字符串哈希（36 章） |
# 找所有出现位置的「正确」Python 写法（比手写 KMP 快）
def find_all(t, p):
res = []
i = t.find(p) # find 找不到返回 -1，正好当循环出口
while i >= 0:
res.append(i)
i = t.find(p, i + 1) # 第二个参数是起始搜索位置；+1 允许重叠，+len(p) 则不重叠
return res
注意这个写法在极端数据上会退化：如果 \(p\) 在 \(t\) 中出现了 \(O(n)\) 次， 每次
find都要重新初始化 two-way 算法的预处理（\(O(m)\)），总代价 \(O(nm/1)\)。 出现次数很多且 \(m\) 很大时，KMP 反而更稳。但这种数据很罕见。
那为什么还要学 KMP？ 因为下面这些事 find 做不到：
71.5 周期性质：KMP 真正不可替代的用途¶
设 \(|s| = n\)，\(\pi[n-1]\) 是整个串的最长 border 长度。
性质一：最小周期¶
而且：当且仅当 \(n \bmod (n - \pi[n-1]) = 0\) 时，\(s\) 由整数个循环节拼成。
def min_period(s):
"""返回 s 的最小周期长度 p（s[i] == s[i+p] 对所有合法 i 成立）。
若 len(s) % p == 0，则 s 恰好由 len(s)//p 个循环节拼成；
否则 s 只是「以 p 为周期的串」的一个前缀。
"""
n = len(s)
pi = prefix_function(s)
# 最长 border 长 pi[n-1]，把它从右端对齐回左端要平移 n-pi[n-1] 位，
# 这个平移量就是最小周期
return n - pi[n - 1]
验证：
| \(s\) | \(\pi[n-1]\) | 最小周期 | \(n \bmod p = 0\)？ | 结论 |
|---|---|---|---|---|
abcabcabc |
6 | 3 | ✅ | 由 3 个 abc 拼成 |
aaaa |
3 | 1 | ✅ | 由 4 个 a 拼成 |
abcab |
2 | 3 | ❌ | 周期 3，但不是整数个 |
abcd |
0 | 4 | ✅ | 只有 1 个循环节（自己） |
这个性质是 KMP 的杀手锏。「最少再添几个字符使串变成周期串」 「求字符串的循环节」「判断能否由某个子串重复得到」——全靠它。
性质二：所有 border¶
\(s\) 的全部 border 长度就是这条链：
def all_borders(s):
"""返回 s 的所有 border 长度（从大到小），不含 s 自身。"""
pi = prefix_function(s)
res = []
k = pi[len(s) - 1] # 整串的最长 border
while k: # 沿失配链一路跳，长度严格递减，跳到 0 结束
res.append(k)
k = pi[k - 1] # 长度 k 的前缀，它自己的最长 border
return res
性质三：每个前缀的最小周期¶
\(\pi\) 数组一次求出所有前缀的 border，所以每个前缀的最小周期是
\(i + 1 - \pi[i]\)——一次 \(O(n)\) 得到 \(n\) 个答案，这是 find 完全办不到的。
71.6 Z 函数（扩展 KMP）¶
定义¶
即 \(s\) 与它从 \(i\) 开始的后缀的最长公共前缀长度。约定 \(z[0] = n\)。
求法：维护「最靠右的匹配段」¶
思想和 Manacher 一模一样（72-回文）： 维护一个已知的匹配区间 \([l, r)\)（满足 \(s[l..r) = s[0..r-l)\)）， 用它对当前位置做镜像预测，再从预测值继续暴力扩展。
def z_function(s):
"""Z 函数：z[i] = s 与 s[i:] 的最长公共前缀长度。O(n)。"""
n = len(s)
z = [0] * n
if n == 0:
return z
z[0] = n # 约定：s 与自己的公共前缀就是整串
l = r = 0 # 最靠右的匹配段 [l, r)，满足 s[l:r] == s[0:r-l]
for i in range(1, n):
if i < r: # i 落在已知段内，可以借用镜像位置的结论
zi = z[i - l] # i 关于段首 l 的镜像位置
ri = r - i # 已知段在 i 右边还剩多少字符可信
z[i] = zi if zi < ri else ri # ★ 下界 = min(镜像值, 区间剩余)
while i + z[i] < n and s[z[i]] == s[i + z[i]]:
z[i] += 1 # 超出已知段的部分没有信息，只能逐位暴力扩
if i + z[i] > r:
l, r = i, i + z[i] # 扩出了更靠右的边界，换成新的已知段
return z
为什么是 \(O(n)\)：每次 while 扩展一步，\(r\) 必然增大一步，而 \(r \le n\) 且单调不减。
Z 函数做匹配¶
def z_search(t, p, sep=b"\x00"):
"""用 Z 函数在 t 中找 p 的所有出现。O(n + m)。"""
m = len(p)
s = p + sep + t # t 从下标 m+1 开始（p 占 m 位，sep 占 1 位）
z = z_function(s)
# z[i] >= m 表示从 i 开始至少有 m 个字符与 s 的开头（即 p）一致；
# 有 sep 挡着，z[i] 不可能超过 m。减去偏移 m+1 即为 t 中的下标
return [i - m - 1 for i in range(m + 1, len(s)) if z[i] >= m]
\(\pi\) 与 \(z\) 的分工¶
| 前缀函数 \(\pi\) | Z 函数 | |
|---|---|---|
| 语义 | 每个前缀的最长 border | 每个后缀与整串的 LCP |
| 求周期/循环节 | ✅ 首选 | ⚠️ 可以但绕 |
| 求所有 border | ✅ | ❌ |
| 求「\(s\) 的每个后缀和 \(s\) 的公共前缀」 | ❌ | ✅ 首选 |
| 判「\(p\) 在 \(t\) 的每个位置匹配了多长」 | ⚠️ 要改造 | ✅ 直接就是 |
| 实现难度 | 简单 | 中等 |
| Python 常数 | 快（实测 \(10^6\) 约 0.08 s） | 慢约 3 倍（约 0.22 s） |
实战选择：默认写 \(\pi\)。只有明确需要「每个位置的 LCP 长度」时才用 Z 函数。 大部分「扩展 KMP」题也能用字符串哈希 + 二分做（\(O(n \log n)\) 但代码短）。
71.7 例题¶
BISHI92 【模板】前缀函数（kmp）（中等）¶
\(T \le 2\times10^6\) 组数据，每组给一个长 \(n\) 的小写字母串（\(\sum n \le 2\times10^6\)）， 输出它的前缀函数 \(\pi_1, \pi_2, \dots, \pi_n\)，一行一组，空格分隔。 特殊测试点 11–15：仅使用一个字符构建串。 题面见 BISHI92 原题（牛客）。 题解见
solutions/BISHI92.py（已用官方样例验证）。
这题是纯模板 + 纯 IO 压力测试。 算法就是 71.2 的十行递推， 但 \(\sum n = 2\times10^6\)、输出 \(2\times10^6\) 个整数（4–14 MB）， IO 才是真正的对手。
import sys
def main():
data = sys.stdin.buffer.read().split()
t = int(data[0])
out = []
p = 1
for _ in range(t):
n = int(data[p]); s = data[p + 1]; p += 2 # 全程 bytes，不 decode
pi = [0] * n # 每组重开一张表，k 也必须跟着归零
k = 0 # 候选 border 长度 = 下一个要比的下标
for i in range(1, n): # pi[0] 恒为 0，直接跳过
c = s[i] # bytes 取出来是 int，整数比较比字符对象快
while k and s[k] != c: # 沿失配链回退，均摊 O(1)
k = pi[k - 1] # 换成次长的候选，而不是从头再来
if s[k] == c:
k += 1 # 候选前缀加长一位
pi[i] = k
out.append(" ".join(map(str, pi))) # 每组先拼成一行，最后统一输出
sys.stdout.write("\n".join(out) + "\n") # 2e6 个整数只能一次写出，逐行 print 必 TLE
main()
复杂度 \(O(\sum n)\)。
关于「测试点 11–15 只用一个字符」：出题人想卡的是没写失配链回退的假 KMP。
但有趣的是，\(s = \texttt{aaaa}\cdots\) 恰恰是 KMP 的最快情况——
\(k\) 一路 \(+1\) 从不回退。真正让内层 while 跑得多的是 aaaab 这类结构，
但均摊仍然是线性的。
四个 Python 要点：
| 要点 | 理由 |
|---|---|
全程 bytes，不 decode |
s[i] 得到 int，整数比较比字符串对象比较快 |
c = s[i] 先取出来 |
内层 while 里少一次索引 |
逻辑装进 main() |
局部变量走 LOAD_FAST，比全局快 20–30% |
" ".join(map(str, pi)) |
map + C 层 str，比列表推导略快 |
读入格式的坑：每组是「先一个整数 \(n\)，再一个长度 \(n\) 的字符串」，
两者在同一行。但用 split() 按 token 读就完全不用关心换行位置——
这是 token 流读法相对于按行读的最大好处，见
20-输入输出处理。
Python 现实性评估：\(\sum n = 2\times10^6\)，主循环 \(2\times10^6\) 次 （实测 \(10^6\) 的前缀函数约 0.08 s，所以主循环约 0.16 s）， 但输出 \(2\times10^6\) 个整数的
map(str, ...)+join约 0.5–1 s。 时限「其他语言 4 秒」，能过，但 IO 一定要一次性做。 若逐行
71.8 本章速查¶
| 要点 | 结论 |
|---|---|
| 核心结论 | Python 里找子串一律用 find/in，手写 KMP 慢 10–240 倍 |
| KMP 的真正价值 | 前缀函数：border、最小循环节、所有周期 |
| \(\pi[i]\) 定义 | \(s[0..i]\) 的最长「真前缀 = 真后缀」长度 |
| 递推核心 | 失配就沿链回退 k = pi[k-1] |
| 复杂度 | 均摊 \(O(n)\)（\(k\) 总增量 \(\le n\)） |
| 匹配时允许重叠 | 命中后 k = pi[k-1] |
| 匹配时不许重叠 | 命中后 k = 0 |
| 拼接法 | p + sep + t，分隔符不能省 |
| 最小周期 | \(n - \pi[n-1]\) |
| 整数个循环节 | 且 \(n \bmod (n-\pi[n-1]) = 0\) |
| 所有 border | \(\pi[n-1] \to \pi[\pi[n-1]-1] \to \cdots\) |
| 每个前缀的最小周期 | \(i+1-\pi[i]\)，一次 \(O(n)\) 出全部 |
| \(z[i]\) 定义 | \(s\) 与 \(s[i:]\) 的最长公共前缀，\(z[0]=n\) |
| Z 函数思想 | 维护最右匹配段 \([l,r)\) + 镜像预测（同 Manacher） |
| \(\pi\) vs \(z\) 的常数 | \(z\) 约慢 3 倍，默认写 \(\pi\) |
| 数据表示 | 全程 bytes，比较 int 最快 |
| 输出大量整数 | 一次 "\n".join + 一次 write |
| 看到什么 → 想到什么 |
|---|
| 「\(t\) 里有没有 \(p\)」 |
| 「\(p\) 出现了几次」 |
| 「最小循环节 / 由某串重复而成」 |
| 「所有既是前缀又是后缀的串」 |
| 「每个前缀的最长 border」 |
| 「每个位置和开头能匹配多长」 |
| 「任意两个子串是否相等」 |
| 「多模式串同时匹配」 |
| 「最长回文子串」 |