第 32 章字符串匹配 (String Matching)

核心结论

字符串匹配问题形式化：给定文本数组 \(T[1..n\)] 和模式数组 \(P[1..m\)]（\(m \leq n\)），找所有 shift \(s\)（\(0 \leq s \leq n-m\)）使得 \(T[s+1..s+m\) = P[1..m]]。
朴素算法：暴力枚举所有 shift，最坏情形 \(\Theta((n-m+1)m)\)；当 \(m = \lfloor n/2 \rfloor\) 时达 \(\Theta(n^2)\)——简单但忽略了已匹配信息。
Rabin-Karp 算法：用滚动哈希将串当整数比较；预处理 \(\Theta(m)\)，最坏匹配 \(\Theta((n-m+1)m)\)，但平均情形（少量有效 shift + 选大素数 \(q > m\)）为 \(O(n+m)\)。
有限自动机方法：为模式 \(P\) 建 DFA（state = 最长匹配前缀长度），转移函数 \(\delta(q,a) = \sigma(P_q a)\) 由后缀函数定义；预处理 \(O(m\lvert \Sigma \rvert)\)，匹配 \(\Theta(n)\)。
Knuth-Morris-Pratt (KMP) 算法：用「前缀函数」\(\pi[q\)]（最长真前缀同时是 \(P_q\) 的后缀）按需模拟转移函数；预处理 \(\Theta(m)\)，匹配 \(\Theta(n)\)，且与字母表大小无关。
关键工具：后缀函数 \(\sigma(x) = \max\{k : P_k = x\}\) 与重叠后缀引理（Lemma 32.1），是 DFA 正确性证明的核心。

本章主旨

本章系统讲述在文本 \(T\) 中查找模式 \(P\) 出现位置的四种算法：从直白的暴力枚举，到用哈希加速比较、用自动机按状态推进、再到 KMP 用模式自身的信息避免冗余比较。后三种都展示了相同的核心思想——充分利用一次匹配失败后已获得的信息来跳过无效 shift——只是利用方式不同。Rabin-Karp 用数论技巧将子串比较转为常数时间整数比较；有限自动机把整个文本扫描抽象为状态机；KMP 用前缀函数在 amortized 意义下"即时"计算转移。最终 KMP 是最实用的选择：预处理与匹配都是线性，与字母表大小无关。

一、核心概念

本章围绕 5 个核心概念展开：从朴素算法的低效出发，逐步引入利用已匹配信息的哈希、自动机、前缀函数技术，最后给出统一的后缀函数框架。

概念	定义 + 重要性	实现提示
朴素字符串匹配 (Naive)	枚举每个 shift \(s\)，逐字符比较 \(P[1..m\)] 与 \(T[s+1..s+m\)]；信息复用率为 0。	§32.1；最坏情形 \(\Theta((n-m+1)m)\)；是改进算法的对照基准。
Rabin-Karp 哈希匹配	把串看作 \(d\)-进制数并取模 \(q\)，相邻窗口用常数时间递推更新哈希；命中再验证。	§32.2；匹配时间最坏仍 \(\Theta((n-m+1)m)\)，但期望为 \(O(n+m)\)（当 \(q \geq m\) 且有效 shift 少）；式 32.2 是递推核心。
字符串匹配有限自动机	DFA 状态 \(q\) 表示「已匹配 \(P\) 的最长前缀长度」；转移函数由后缀函数 \(\delta(q,a)=\sigma(P_q a)\) 定义。	§32.3；每字符一次转移，匹配 \(\Theta(n)\)；预处理 \(O(m\lvert \Sigma \rvert)\)；式 32.4 是转移定义。
Knuth-Morris-Pratt 前缀函数	前缀函数 \(\pi[q\) = \max\{k < q : P_k = P_q\}]，匹配失败时把 \(q\) 回退到 \(\pi[q\)] 而非归零；amortized 线性。	§32.4；匹配与预处理都 \(\Theta(n)\)/\(\Theta(m)\)，与 \(\lvert \Sigma \rvert\) 无关；式 32.7 与 Lemma 32.5 是正确性核心。
后缀函数 (Suffix Function)	后缀函数 \(\sigma(x) = \max\{k : P_k = x\}\) 把任意串映射到「作为 \(P\) 后缀的最长前缀长度」；是 DFA 转移函数的定义基础。	§32.3；式 32.3 定义；Lemma 32.2（\(\sigma(xa) \leq \sigma(x)+1\)）与 Lemma 32.3（递归）是关键引理。

概念

定义 + 重要性

实现提示

朴素字符串匹配 (Naive)

枚举每个 shift \(s\)，逐字符比较 \(P[1..m\)] 与 \(T[s+1..s+m\)]；信息复用率为 0。

§32.1；最坏情形 \(\Theta((n-m+1)m)\)；是改进算法的对照基准。

Rabin-Karp 哈希匹配

把串看作 \(d\)-进制数并取模 \(q\)，相邻窗口用常数时间递推更新哈希；命中再验证。

§32.2；匹配时间最坏仍 \(\Theta((n-m+1)m)\)，但期望为 \(O(n+m)\)（当 \(q \geq m\) 且有效 shift 少）；式 32.2 是递推核心。

字符串匹配有限自动机

DFA 状态 \(q\) 表示「已匹配 \(P\) 的最长前缀长度」；转移函数由后缀函数 \(\delta(q,a)=\sigma(P_q a)\) 定义。

§32.3；每字符一次转移，匹配 \(\Theta(n)\)；预处理 \(O(m\lvert \Sigma \rvert)\)；式 32.4 是转移定义。

Knuth-Morris-Pratt 前缀函数

前缀函数 \(\pi[q\) = \max\{k < q : P_k = P_q\}]，匹配失败时把 \(q\) 回退到 \(\pi[q\)] 而非归零；amortized 线性。

§32.4；匹配与预处理都 \(\Theta(n)\)/\(\Theta(m)\)，与 \(\lvert \Sigma \rvert\) 无关；式 32.7 与 Lemma 32.5 是正确性核心。

后缀函数 (Suffix Function)

后缀函数 \(\sigma(x) = \max\{k : P_k = x\}\) 把任意串映射到「作为 \(P\) 后缀的最长前缀长度」；是 DFA 转移函数的定义基础。

§32.3；式 32.3 定义；Lemma 32.2（\(\sigma(xa) \leq \sigma(x)+1\)）与 Lemma 32.3（递归）是关键引理。

二、详细笔记

2.1 朴素字符串匹配 (Naive String Matcher)

What：对每个可能 shift \(s \in [0, n-m\)]，从左到右逐字符比较 \(P[1..m\)] 与 \(T[s+1..s+m\)]；匹配则输出 \(s\)。

Why：作为对照基准——所有改进算法的目标都是降低「重新检查已匹配信息」的成本；朴素算法忽略这部分，因此最坏情形是二次的。

How：

步骤	描述
输入	文本 \(T[1..n\)]，模式 \(P[1..m\)]，\(m \leq n\)
外层循环	\(s\) 从 0 到 \(n-m\)
内层循环	逐字符比较 \(P[j\)] 与 \(T[s+j\)]；遇不等则跳出
输出	报告所有使 \(P = T_{s+m}\) 成立的 shift \(s\)

步骤

描述

输入

文本 \(T[1..n\)]，模式 \(P[1..m\)]，\(m \leq n\)

外层循环

\(s\) 从 0 到 \(n-m\)

内层循环

逐字符比较 \(P[j\)] 与 \(T[s+j\)]；遇不等则跳出

输出

报告所有使 \(P = T_{s+m}\) 成立的 shift \(s\)

最坏情形（\(T = a^n, P = a^m\)）每次都需 \(m\) 次比较，共 \(\Theta((n-m+1)m)\)；当 \(m = \lfloor n/2 \rfloor\) 时为 \(\Theta(n^2)\)。

When：模式极短、字母表很小、随机串场景下（期望比较次数 \(O(n-m+1)\)）仍可接受；其他场景应改用 KMP 或 Rabin-Karp。

Example：在 \(T = \text{acaabc}\) 中查 \(P = \text{aab}\)：依次尝试 \(s=0,1,2,3\)，仅 \(s=2\) 命中——朴素算法总共做了 \(4 \times 3 = 12\) 次比较。

2.2 Rabin-Karp 算法

What：把长度为 \(m\) 的串当作 \(d\)-进制数；用滚动哈希在常数时间内从 \(t_s\) 更新到 \(t_{s+1}\)，哈希匹配后再做一次字符比较排除假阳性（spurious hit）。

Why：当字母表是数字/字符时，把串比较转为整数比较可显著加速；滚动哈希保证每次窗口滑动为 \(O(1)\)；同时哈希便于推广到二维模式匹配、多模式搜索等场景。

How：

\[\begin{aligned} t_{s+1} &\equiv \bigl(d\,t_s - T[s+1]\,h\bigr) + T[s+m+1] \pmod{q} \\ h &\equiv d^{m-1} \pmod{q} \end{aligned}\]

阶段	操作	时间
预处理	计算 \(p \bmod q\) 与 \(t_0 \bmod q\)，常数 \(h = d^{m-1} \bmod q\)	\(\Theta(m)\)
匹配	滚动更新 \(t_s\)，哈希相等时逐字符验证	最坏 \(\Theta((n-m+1)m)\)；期望 \(O(n+m)\)

阶段

操作

时间

预处理

计算 \(p \bmod q\) 与 \(t_0 \bmod q\)，常数 \(h = d^{m-1} \bmod q\)

\(\Theta(m)\)

匹配

滚动更新 \(t_s\)，哈希相等时逐字符验证

最坏 \(\Theta((n-m+1)m)\)；期望 \(O(n+m)\)

假阳性概率 ≈ \(1/q\)；选大素数 \(q > m\) 时期望命中数小，期望匹配时间降至 \(O(n+m)\)。

When：期望有效 shift 数量少（\(O(1)\)）、字母表小（如核酸序列、基因比对）、需要二维/多模式扩展时；不适合需要严格最坏情形保证的场景。

Example：\(\Sigma = \{0..9\}\), \(q = 13\), \(m = 5\)：匹配 \(P = 31415\)，则 \(p \bmod 13 = 7\)；扫描文本时只在 hash = 7 处停留验证。

2.3 字符串匹配有限自动机

What：为模式 \(P\) 构造 DFA，状态集 \(\{0, 1, \ldots, m\}\)，起始 0、唯一接受态 \(m\)；转移函数 \(\delta(q, a) = \sigma(P_q a)\)，其中后缀函数 \(\sigma(x) = \max\{k : P_k = x\}\)。

Why：DFA 把字符串匹配转化为状态机扫描；每读一个字符走一次转移，故匹配 \(\Theta(n)\)，与文本长度严格成正比；适合需要最坏情形保证的实时系统。

How：

\[\delta(q, a) = \sigma(P_q a), \qquad \sigma(x) = \max\{k : P_k = x\}\]

不变量	形式
主循环不变式	读入 \(T[1..i\)] 后状态 = \(\sigma(T_i)\)（即与已读后缀相等的 \(P\) 最长前缀长度）
接受	状态 = \(m\) ⟺ \(P = T_i\)（找到一个匹配）
关键引理	Lemma 32.3: \(\sigma(xa) = \sigma(\sigma(x)\text{'s }P\text{-prefix extended by }a)\)

不变量

形式

主循环不变式

读入 \(T[1..i\)] 后状态 = \(\sigma(T_i)\)（即与已读后缀相等的 \(P\) 最长前缀长度）

接受

状态 = \(m\) ⟺ \(P = T_i\)（找到一个匹配）

关键引理

Lemma 32.3: \(\sigma(xa) = \sigma(\sigma(x)\text{'s }P\text{-prefix extended by }a)\)

匹配循环：

步骤	描述
1	\(q \gets 0\)
2	for \(i = 1\) to \(n\): \(q \gets \delta(q, T[i\))]
3	if \(q == m\): 输出 shift \(i - m\)

预处理转移函数 naive 是 \(O(m^3 \lvert \Sigma \rvert)\)（COMPUTE-TRANSITION-FUNCTION）；用引理 32.5 与练习 32.4-8 的技巧可降到 \(O(m \lvert \Sigma \rvert)\)。

When：需要 worst-case 线性匹配、对预处理时间不敏感、字母表小（\(\lvert \Sigma \rvert\) 小）时；大字母表下 KMP 更合适（与 \(\lvert \Sigma \rvert\) 无关）。

Example：模式 \(P = \text{ababaca}\) 的 DFA（Figure 32.7）：从状态 0 开始，依次读 \(\text{abababacaba}\)，第 9 字符后到达接受态 7，shift = 9 - 7 = 2。

2.4 Knuth-Morris-Pratt (KMP) 算法

What：用「前缀函数」\(\pi[q\) = \max\{k < q : P_k = P_q\}] 在匹配失败时回退到 \(\pi[q\)]，避免 DFA 的大表；同时保留线性匹配时间。

Why：DFA 预处理开销与 \(\lvert \Sigma \rvert\) 成正比（DNA 序列 \(\lvert \Sigma \rvert = 4\) 可接受，但 ASCII \(\lvert \Sigma \rvert = 128\) 则昂贵）；KMP 用大小为 \(m\) 的 \(\pi\) 数组在 amortized 意义下模拟 \(\delta\)，与 \(\lvert \Sigma \rvert\) 无关。

How：

步骤	KMP-MATCHER
COMPUTE-PREFIX-FUNCTION	主循环
扫描 \(i = 1..n\)，维护已匹配长度 \(q\)	失配回退
while \(q > 0\) 且 \(P[q+1\) \neq T[i]]: \(q \gets \pi[q\)]	匹配成功
if \(P[q+1\) == T[i]]: \(q \gets q + 1\)	报告
if \(q == m\): 输出 \(i-m\)，并 \(q \gets \pi[q\)] 继续	预处理
—	for \(q = 2..m\): 计算 \(\pi[q\) = \max\{k < q : P_k = P_q\}]

步骤

KMP-MATCHER

COMPUTE-PREFIX-FUNCTION

主循环

扫描 \(i = 1..n\)，维护已匹配长度 \(q\)

失配回退

while \(q > 0\) 且 \(P[q+1\) \neq T[i]]: \(q \gets \pi[q\)]

匹配成功

if \(P[q+1\) == T[i]]: \(q \gets q + 1\)

报告

if \(q == m\): 输出 \(i-m\)，并 \(q \gets \pi[q\)] 继续

预处理

—

for \(q = 2..m\): 计算 \(\pi[q\) = \max\{k < q : P_k = P_q\}]

时间复杂度： * 预处理 COMPUTE-PREFIX-FUNCTION：aggregate analysis，\(\Theta(m)\)（while 循环至多 \(m-1\) 次） * 匹配 KMP-MATCHER：类似分析，\(\Theta(n)\)

When：实际工程的默认选择——匹配时间与字母表大小无关；特别适合文本编辑器的查找/替换、生物序列比对、编译器词法分析等。

Example：模式 \(P = \text{ababaca}\) 的 \(\pi = [0,0,1,2,3,0,1\)]（Figure 32.11）；在 \(T = \text{abababacaba}\) 上从 \(q=0\) 起逐字符推进。

2.5 后缀函数 (Suffix Function) 与引理

What：后缀函数 \(\sigma(x) = \max\{k : P_k = x\}\) 将任意串映射为「作为 \(P\) 后缀的最长前缀长度」；空串永远满足，故 \(\sigma\) 良定义。

Why：\(\sigma\) 是 DFA 转移函数的定义（式 32.4），也是 KMP 正确性的核心工具——它把「匹配进展」和「回退距离」用同一个量刻画。

How：

命题	内容
定义 (式 32.3)	\(\sigma(x) = \max\{k : P_k \sqsupset x\}\)
Lemma 32.2	\(\sigma(xa) \leq \sigma(x) + 1\)（每次加字符最多多匹配一位）
Lemma 32.3	\(\sigma(xa) = \sigma(P_{\sigma(x)} a)\)（递归：把已知最长的 \(P\) 前缀接上 \(a\)，再取 \(\sigma\))
Lemma 32.1 (重叠后缀)	若 \(x \sqsupset z\) 且 \(y \sqsupset z\)，则 \(x \sqsupset y\)（短的「赢」）
Theorem 32.4	DFA 不变式：\(\phi(T_i) = \sigma(T_i)\)（状态机跟踪当前最长匹配前缀）

命题

内容

定义 (式 32.3)

\(\sigma(x) = \max\{k : P_k \sqsupset x\}\)

Lemma 32.2

\(\sigma(xa) \leq \sigma(x) + 1\)（每次加字符最多多匹配一位）

Lemma 32.3

\(\sigma(xa) = \sigma(P_{\sigma(x)} a)\)（递归：把已知最长的 \(P\) 前缀接上 \(a\)，再取 \(\sigma\))

Lemma 32.1 (重叠后缀)

若 \(x \sqsupset z\) 且 \(y \sqsupset z\)，则 \(x \sqsupset y\)（短的「赢」）

Theorem 32.4

DFA 不变式：\(\phi(T_i) = \sigma(T_i)\)（状态机跟踪当前最长匹配前缀）

When：设计新的串匹配算法或证明现有算法正确性时；Lemma 32.3 是 KMP 与 DFA 等价性的关键。

Example：\(P = \text{ab}\) 时，\(\sigma(\varepsilon) = 0\)，\(\sigma(\text{ccaca}) = 1\)，\(\sigma(\text{ccab}) = 2\)；这些值与 DFA 在状态 0/1/2 读入对应字符串后的转移目标一一对应。

三、关键图表

核心公式对照表

公式编号

内容

式 32.1

朴素滚动：\(t_{s+1} = 10(t_s - 10^{m-1} T[s+1\)) + T[s+m+1]]

式 32.2

Rabin-Karp 取模滚动：\(t_{s+1} \equiv (d \cdot t_s - T[s+1\) \cdot h + T[s+m+1]) \pmod{q}]

式 32.3

后缀函数定义：\(\sigma(x) = \max\{k : P_k \sqsupset x\}\)

式 32.4

DFA 转移：\(\delta(q, a) = \sigma(P_q a)\)

式 32.5

DFA 主不变式：\(\phi(T_i) = \sigma(T_i)\)

式 32.6

KMP 下一个有效 shift：\(P[1..k\) = T[s'+1..s'+k]]，\(s' = s + (q-k)\)

四、思维导图

mindmap
  root((第 32 章 字符串匹配))
    问题形式化
      文本与模式
      valid shift
      字母表
    朴素算法
      暴力枚举
      最坏二次
      信息复用率0
    Rabin-Karp
      滚动哈希
      取模q
      期望线性
      多模式扩展
    有限自动机
      后缀函数sigma
      转移函数delta
      最坏线性
      与字母表有关
    KMP
      前缀函数pi
      amortized回退
      与字母表无关
      实际首选

五、重点与易错点

字符串匹配复杂度对比要分清最坏与期望：Rabin-Karp 最坏仍为 \(\Theta((n-m+1)m)\)，只有期望才是 \(O(n+m)\)；朴素算法虽无预处理但最坏是二次。
朴素算法忽略「已匹配前缀中的内部结构」——例如若 \(P = \text{aaab}\) 且 shift 0 命中，可立即排除 shift 1/2/3，因为 \(T[4\) = b ≠ a]；改进算法的核心就是利用这种信息。
Rabin-Karp 的假阳性（spurious hit）必须做字符级验证；只在哈希相等时输出是错误的。
DFA 的转移函数定义 \(\delta(q, a) = \sigma(P_q a)\) 看似任意，实际是关键——保持不变式「状态 = 与已读后缀相等的 P 最长前缀长度」。
KMP 的 \(\pi[1\) = 0]（永远是 0，因为要求 \(k < q\)）；很多人误写成 \(\pi[1\) = 1]。
Lemma 32.3 的递推等价于「已知状态 \(q\)，下一步转移只依赖 \(P_q a\)」——这就是 KMP 不需要完整 DFA 表的原因。
时间复杂度分析用 aggregate method：while 循环总迭代次数被外层 for 循环的增量上界限制。
字母表大小 \(\lvert \Sigma \rvert\) 是选择算法的重要因素——DFA 预处理 \(O(m\lvert \Sigma \rvert)\) 与之成正比，KMP 与之无关；DNA \(\lvert \Sigma \rvert=4\) 与 ASCII \(\lvert \Sigma \rvert=128\) 差距明显。
子串与子序列不同：串匹配要求连续，LCS 是子序列；混淆会导致问题形式化错误。
字符串比较的代价：朴素与 KMP 在「最长公共前缀长度」上是线性的（§32 注释），Rabin-Karp 用常数代价换取期望正确性。
模式与文本长度关系 \(m \leq n\) 是默认假设；若 \(m > n\) 则平凡地输出 0 个 shift。
推广到二维模式匹配（习题 32.2-3）：把二维哈希定义为子矩阵元素加权和，滚动更新时类似处理。

第 32 章 字符串匹配 (String Matching)

核心结论

一、核心概念

二、详细笔记

2.1 朴素字符串匹配 (Naive String Matcher)

2.2 Rabin-Karp 算法

2.3 字符串匹配有限自动机

2.4 Knuth-Morris-Pratt (KMP) 算法

2.5 后缀函数 (Suffix Function) 与引理

三、关键图表

四、思维导图

五、重点与易错点

第 32 章字符串匹配 (String Matching)