KMP字符串匹配

1. 概述与学习目标

1.1 什么是字符串匹配问题

字符串匹配（String Matching / Pattern Matching）是计算机科学最古老、最基础的问题之一：给定文本串 $T = T[0..n-1]$（长度 $n$）与模式串 $P = P[0..m-1]$（长度 $m$），寻找 $P$ 在 $T$ 中所有出现位置 $s$，使得 $T[s..s+m-1] = P$。该问题在以下场景中被高频调用：

• 文本编辑器：查找与替换（Vim、VS Code、Sublime）
• 命令行工具：grep、sed、awk 的核心引擎
• 静态分析：ESLint、Clang-Tidy 的规则匹配
• 生物信息学：DNA 序列 read 比对（BWA、Bowtie）
• 网络安全：入侵检测系统（Snort、Suricata）的规则引擎
• 数据库：SQL LIKE 模式匹配、全文检索的 substring 查询
• Web 搜索：浏览器 Ctrl+F、爬虫 URL 去重

字符串匹配算法的设计核心是回答两个问题：

1. 最坏时间复杂度下界是多少？ Cook 1971 与 Knuth-Morris-Pratt 1977 证明：在确定性算法框架下，最坏情况至少需要 $\Omega(n+m)$ 次字符比较
2. 如何达到这一下界？ KMP 是首个达到 $\Theta(n+m)$ 最坏时间复杂度的算法，其核心创新是利用模式串自身结构（部分匹配表）避免文本指针回退

1.2 KMP 的核心思想

朴素字符串匹配（Naive String Matching）在最坏情况下需要 $O(nm)$ 时间，例如 $T = \text{"AAAA...A"}$、$P = \text{"AAAA...AB"}$ 时，每次失配都让模式串仅前进 1 位，共 $(n-m+1) \cdot m \approx O(nm)$ 次比较。

KMP 的关键洞察：失配时不要丢弃已匹配的信息。当 $T[i]$ 与 $P[j]$ 失配时，我们已知 $T[i-j..i-1] = P[0..j-1]$；如果模式串 $P$ 自身存在”前缀 = 后缀”的结构（如 P = "ABAB" 的前缀 "AB" 等于后缀 "AB"），则可以将 $P$ 右移若干位，使 $P$ 的某个前缀对齐到 $T$ 已匹配部分的后缀，从而跳过必然失败的比较。

文本:    A B A B A B C
模式:    A B A B C
              ↑ 失配（T[4]='A'，P[4]='C'）

朴素做法：模式右移 1 位，重新比较
KMP 做法：发现 "ABAB" 的最长公共前后缀为 "AB"
          模式右移 2 位，使 P[0..1] 对齐 T[2..3]
          直接从 T[4] 与 P[2] 开始比较

文本:    A B A B A B C
模式:        A B A B C
              ↑ 从这里继续，跳过必然失败的比较

实现这一思想需要预先计算**部分匹配表（PMT）**或等价的 next 数组，记录 $P$ 每个前缀的最长相等前后缀长度。next 数组的构建本身也是一个 $O(m)$ 的精妙过程，KMP 算法本质上是模式串与自身的匹配过程。

1.3 学习目标

完成本章学习后，读者应能够：

1. 记忆（Remember）：KMP 三阶段流程、next 数组形式化递推式、Knuth-Morris-Pratt 1977 SIAM J. Comp. 6(2):323-350 论文核心贡献
2. 理解（Understand）：Morris 1970、Pratt 1970 独立发现 KMP 与 Knuth 1970 复杂度证明的演进脉络，Cook 1971 IFIP 71 对 KMP 设计动机的影响
3. 应用（Apply）：使用 KMP 求解字符串匹配、最小循环节、字符串周期性等问题，编写 Python/C++/Java 三语言实现
4. 分析（Analyze）：基于”文本指针单调不减、模式指针摊还 $O(1)$“的论证方法证明 KMP 时间复杂度 $\Theta(n+m)$
5. 评估（Evaluate）：KMP 与 Boyer-Moore 1977、Rabin-Karp 1987、Aho-Corasick 1975、Suffix Array 的优劣对比
6. 设计（Design）：KMP 自动机、Aho-Corasick 多模式自动机在敏感词过滤、IDS、DNA 比对中的应用
7. 创造（Create）：基于 KMP 设计代码静态分析器、日志模式匹配引擎、DNA motif 发现工具

2. 历史动机与演进

2.1 字符串匹配问题的早期历史（1960s）

字符串匹配问题在计算机科学早期的文本编辑器（如 TECO、QED）中已有迫切需求。1968 年，Thompson 在贝尔实验室开发 QED 文本编辑器时实现了正则表达式搜索引擎（Thompson 1968《Regular Expression Search Algorithm》CACM 11(6):419-422），将正则表达式编译为 NFA 然后模拟执行。这是字符串匹配问题的早期形式化，但 NFA 模拟的最坏复杂度为 $O(nm)$，无法满足大规模文本搜索需求。

1970 年前后，两个独立的研究脉络几乎同时发现了线性时间字符串匹配算法：

• Morris 路线：James H. Morris 在 Carnegie Mellon University 攻读博士期间，参与设计文本编辑器时遇到字符串匹配性能瓶颈。他从有限状态自动机的角度出发，发现模式串可以预编译为一个状态机，使文本指针无需回退。Morris 1970 在未发表的草稿中描述了这一算法（后于 Knuth-Morris-Pratt 1977 论文中正式发表）
• Pratt 路线：Vaughan R. Pratt 在 Stanford University 攻读博士期间，受 Knuth 指导研究算法分析。Pratt 从 Cook 1971 IFIP 71 论文《Linear time simulation of deterministic two-way pushdown automata》的证明思路中汲取灵感，独立推导出线性时间字符串匹配算法

1970 年 Knuth 在与 Morris、Pratt 的交流中整合两者的思路，并完成了严格的复杂度证明。三人合作的论文在 1970 年代初期以技术报告形式流传，但正式发表于 1977 年 SIAM Journal on Computing 6(2):323-350，DOI: 10.1137/0206024。这一延迟发表的原因是 Knuth 当时正集中精力撰写 TAOCP Vol.4，并希望论文中的复杂度证明达到发表级别。

2.2 Cook 1971 的启发

Stephen A. Cook 1971 在 IFIP Congress 71 上发表论文《Linear time simulation of deterministic two-way pushdown automata》，证明确定性双向下推自动机（Deterministic Two-Way Pushdown Automaton, D2PDA）可在 $O(n)$ 时间内被模拟。Cook 的证明思路：

1. D2PDA 在输入带上左右移动，状态转移可能压栈或弹栈
2. 通过分析栈的”高度变化模式”，可以将 D2PDA 的所有移动归约为若干”等价类”
3. 每个等价类的模拟代价是 $O(1)$ 摊还，因此总模拟代价 $O(n)$

字符串匹配问题可以自然地归约为 D2PDA 模拟：构造一个 D2PDA，输入头在 $T$ 上从左到右移动，同时维护栈中已匹配的 $P$ 前缀。失配时，D2PDA 利用栈内容回退到合适的 $P$ 位置继续匹配。Cook 1971 证明这一模拟可在 $O(n)$ 时间内完成，理论上保证了线性时间字符串匹配算法的存在性。

Morris 与 Pratt 正是从 Cook 1971 的构造中提取了显式算法，使其从抽象的自动机模拟变为可执行的代码。Cook 因此获 1982 Turing Award，部分归功于这一贡献。

timeline
    title KMP 算法演进关键里程碑
    1968 : Thompson QED 正则表达式 NFA
    1970 : Morris 独立发现线性匹配算法 (CMU)
    1970 : Pratt 独立发现线性匹配算法 (Stanford)
    1970 : Knuth 整合思路并完成复杂度证明
    1971 : Cook IFIP 71 D2PDA 线性模拟 (理论奠基)
    1975 : Aho-Corasick 多模式扩展 (CACM)
    1977 : KMP 论文正式发表 (SIAM J. Comp.)
    1977 : Boyer-Moore 算法 (CACM)
    1979 : Galil BM 改进至 O(n+m)
    1980 : Horspool BMH 简化变种
    1987 : Karp-Rabin 滚动哈希 (IBM J. Res. Dev.)
    1990 : Sunday 算法 (CACM)
    1994 : Cole BM 紧界 3n / KMP 下界 2n-m
    1997 : Gusfield 字符串算法专著出版
    2022 : CLRS 第 4 版 第 32 章 KMP

2.3 KMP 论文的核心贡献

Knuth-Morris-Pratt 1977《Fast Pattern Matching in Strings》SIAM J. Comp. 6(2):323-350 的核心贡献包括：

1. 算法本身：给出 KMP 算法的显式描述，包括 next 数组（论文中称 $f[j]$）的构建与匹配过程
2. 线性时间复杂度证明：严格证明预处理 $O(m)$、匹配 $O(n)$，总复杂度 $O(n+m)$
3. 下界证明：证明在二字母表 $\Sigma = \{a, b\}$ 上，任何基于”前缀匹配”的算法在最坏情况下至少需要 $2n - m$ 次字符比较。这一下界后被 Cole 1994 改进为紧界
4. next 数组优化：论文给出 next 数组的两种构造方式（含/不含”必然失配”跳过），后者即现代教材中常见的”优化 next”或 nextval
5. 与 Cook 1971 的联系：明确指出 KMP 是 Cook 1971 D2PDA 模拟的特例，从理论上阐释了线性时间的来源

KMP 论文的发表标志着字符串匹配问题从经验性算法上升为具有严格复杂度保证的理论领域，开启了 1980s 字符串算法的黄金时代（包括 Suffix Tree、Suffix Array、BWT 等重大发展）。

2.4 KMP 与同期算法的关系

KMP 与同期提出的字符串匹配算法在算法范式上有本质差异：

其中 $n$ 为文本长度，$m$ 为模式长度，$\sigma$ 为字母表大小，$M$ 为多模式总长度，$z$ 为匹配数。

算法范式的本质差异：

• KMP：从左到右扫描，模式自身结构驱动跳跃，最坏情况严格线性
• Boyer-Moore：从右到左扫描，文本失配字符驱动跳跃，平均最快但最坏情况需 Galil 改进
• Rabin-Karp：哈希值驱动跳跃，本质是 Monte Carlo 算法（可能误判），Las Vegas 版本需 $O(nm)$ 最坏
• Aho-Corasick：KMP 在多模式场景的推广，构建 trie + failure link，是 GNU grep -F 模式、Snort、Suricata 等的核心引擎
• Suffix Array / Automaton：以文本为中心的预处理，模式查询 $O(m \log n)$ 或 $O(m)$，适用于多次查询同一文本

2.5 关键设计决策

KMP 设计中的若干关键决策反映了 1970s 算法研究的哲学转变：

1. 从”在线”到”预处理”：KMP 首次引入”模式串预处理”的概念，将模式自身的结构信息编码为 next 数组。这一思路后被 Aho-Corasick、Suffix Tree、Suffix Array 等扩展至”文本预处理”，开启了两类字符串匹配研究范式
2. 从”字符比较”到”摊还分析”：KMP 的复杂度证明是算法分析史上首次使用”摊还分析”思想的典型案例（早于 Sleator-Tarjan 1985 形式化）。文本指针 $i$ 单调不减、模式指针 $j$ 摊还 $O(1)$ 的论证，本质上是势能法 $\Phi = j$ 的雏形
3. 从”自动机模拟”到”显式代码”：Cook 1971 用抽象的 D2PDA 模拟证明线性时间存在性，KMP 将其具体化为可执行代码。这一”理论可解 → 工程可实现”的转化是算法研究的典型模式
4. next 数组的优化形式：原始 KMP 论文给出 next 数组的”基本形式”与”优化形式”（nextval），后者跳过”必然失配”的中间状态。现代教材普遍采用优化形式

2.6 现代发展

KMP 之后，字符串匹配领域的重大发展包括：

• Suffix Tree（Weiner 1973、McCreight 1976、Ukkonen 1995）：构建文本所有后缀的压缩 trie，支持 $O(m)$ 查询。Gusfield 1997《Algorithms on Strings, Trees, and Sequences》系统化其在生物信息学中的应用
• Suffix Array（Manber-Myers 1990、Kärkkäinen-Sanders 2003）：文本所有后缀的字典序排序数组，空间效率高于 Suffix Tree，是 BWA、Bowtie 等基因组比对工具的基础
• Burrows-Wheeler Transform（Burrows-Wheeler 1994）：用于 bzip2 压缩，FM-Index（Ferragina-Manzini 2000）将其用于 $O(m)$ 字符串匹配，是 BWA 算法的核心
• Backward DAWG Matching（Crochemore et al. 1994）：结合 Suffix Automaton 与 BM 反向扫描，达到次线性平均时间
• Bitap 算法（Baeza-Yates-Gonnet 1992、Wu-Manber 1992）：利用位并行加速字符串匹配，是 agrep、GNU grep 的快速路径

3. 形式化定义

3.1 字符串匹配问题的形式化定义

定义 3.1（字母表与字符串）：字母表（Alphabet）$\Sigma$ 是有限非空字符集合。字符串（String）$S = S[0..|S|-1]$ 是 $\Sigma$ 中字符的有限序列，$|S|$ 称为 $S$ 的长度。空串记为 $\varepsilon$，$|\varepsilon| = 0$。所有 $\Sigma$ 上字符串的集合记为 $\Sigma^*$。

定义 3.2（字符串连接与子串）：字符串 $S$ 与 $T$ 的连接记为 $ST$，$|ST| = |S| + |T|$。$S$ 是 $T$ 的子串（Substring），记为 $S \sqsubseteq T$，若 $\exists u, v \in \Sigma^*$ 使得 $T = uSv$。若 $u = \varepsilon$ 则 $S$ 是 $T$ 的前缀（Prefix），记为 $S \preceq T$；若 $v = \varepsilon$ 则 $S$ 是 $T$ 的后缀（Suffix），记为 $S \succeq T$。

定义 3.3（字符串匹配问题）：给定文本串 $T \in \Sigma^*$（长度 $n$）与模式串 $P \in \Sigma^*$（长度 $m$），字符串匹配问题是寻找所有偏移 $s \in \{0, 1, \ldots, n-m\}$，使得 $P \sqsubseteq T[s..s+m-1]$，即：

$\text{Match}(T, P) = \{s \in \{0, 1, \ldots, n-m\} \mid T[s..s+m-1] = P\}$

若 $n < m$，则 $\text{Match}(T, P) = \emptyset$。

3.2 部分匹配表（PMT）的形式化定义

定义 3.4（最长相等前后缀）：对于字符串 $S$（$|S| \geq 1$），$S$ 的最长相等前后缀长度定义为：

$\text{lps}(S) = \max\{k \in \{0, 1, \ldots, |S|-1\} \mid S[0..k-1] = S[|S|-k..|S|-1]\}$

约定 $\text{lps}(\varepsilon) = 0$。注意 $k \leq |S|-1$ 排除了 $S$ 自身作为前后缀的平凡情况。

定义 3.5（部分匹配表 PMT）：模式串 $P[0..m-1]$ 的部分匹配表（Partial Match Table）是一个长度为 $m$ 的整数数组，定义为：

$\text{PMT}[i] = \text{lps}(P[0..i]) = \max\{k \in \{0, 1, \ldots, i\} \mid P[0..k-1] = P[i-k+1..i]\}$

特别地，$\text{PMT}[0] = 0$（单字符无相等前后缀）。

示例 3.1：$P = \text{"ABABC"}$，求 PMT：

故 $\text{PMT} = [0, 0, 1, 2, 0]$。

3.3 next 数组的形式化定义

next 数组是 PMT 的等价形式，用于在失配时直接给出模式指针的跳转位置。现代教材中存在两种常见约定：

定义 3.6（next 数组，约定 A，CLRS 风格）：next 数组长度为 $m$，定义为：

$\text{next}[j] = \text{lps}(P[0..j-1]) = \max\{k \in \{0, 1, \ldots, j-1\} \mid P[0..k-1] = P[j-k..j-1]\}$

约定 $\text{next}[0] = -1$（哨兵值，表示模式整体右移）。在此约定下，当 $T[i]$ 与 $P[j]$ 失配时，模式指针跳转到 $j' = \text{next}[j]$，文本指针 $i$ 不变。

定义 3.7（next 数组，约定 B，国内教材风格）：next 数组长度为 $m$，定义为：

$\text{next}[j] = \begin{cases} -1 & j = 0 \\ \text{lps}(P[0..j-1]) - 1 & j \geq 1 \end{cases}$

失配时 $j' = \text{next}[j]$，文本指针 $i$ 不变。本文采用约定 A（CLRS 风格），以便与 Pratts 函数 $\pi[j]$ 一致。

示例 3.2：$P = \text{"ABABC"}$，按约定 A：

注意 $\text{next}[j] = \text{PMT}[j-1]$（$j \geq 1$），$\text{next}[0] = -1$（哨兵）。

3.4 KMP 算法的形式化定义

定义 3.8（KMP 算法）：KMP 算法是一个三元组 $\mathcal{KMP} = (\text{BuildNext}, \text{Match}, \text{next})$，其中：

• $\text{BuildNext}: \Sigma^* \to \mathbb{Z}^m$ 将模式串 $P$ 映射为 next 数组
• $\text{Match}: \Sigma^* \times \Sigma^* \times \mathbb{Z}^m \to 2^{\mathbb{N}}$ 给出所有匹配位置
• $\text{next}$ 满足定义 3.6 的递推关系

算法 3.1（KMP 匹配）：

输入：文本 T[0..n-1]，模式 P[0..m-1]
输出：所有匹配偏移 s
1.  next ← BuildNext(P)
2.  j ← 0  // 模式指针
3.  for i ← 0 to n-1 do
4.      while j ≥ 0 and T[i] ≠ P[j] do
5.          j ← next[j]
6.      if j = -1 then
7.          j ← 0
8.      else if T[i] = P[j] then
9.          j ← j + 1
10.     if j = m then
11.         输出 s = i - m + 1
12.         j ← next[j-1]  // 继续搜索下一个匹配
13. end for

算法 3.2（BuildNext，模式串与自身的 KMP 匹配）：

输入：模式 P[0..m-1]
输出：next 数组
1.  next[0] ← -1
2.  j ← -1
3.  for i ← 1 to m-1 do
4.      while j ≥ 0 and P[i] ≠ P[j+1] do
5.          j ← next[j]
6.      if P[i] = P[j+1] then
7.          j ← j + 1
8.      next[i] ← j
9.  end for

3.5 KMP 自动机的形式化定义

定义 3.9（KMP 自动机）：模式串 $P$ 对应的 KMP 自动机是一个确定性有限自动机（DFA）$\mathcal{A}_P = (Q, \Sigma, \delta, q_0, F)$，其中：

• 状态集 $Q = \{0, 1, \ldots, m\}$，状态 $q$ 表示”已匹配 $P$ 的前 $q$ 个字符”
• 字母表 $\Sigma$
• 初始状态 $q_0 = 0$
• 接受状态集 $F = \{m\}$
• 转移函数 $\delta: Q \times \Sigma \to Q$ 定义为：

$\delta(q, c) = \begin{cases} q+1 & \text{若 } q < m \text{ 且 } c = P[q] \\ 0 & \text{若 } q = 0 \text{ 且 } c \neq P[0] \\ \delta(\text{next}[q], c) & \text{若 } q > 0 \text{ 且 } c \neq P[q] \end{cases}$

KMP 自动机的核心思想是将 next 数组隐式地编码到状态转移中，使文本指针 $i$ 单调不减。这一构造后被 Aho-Corasick 1975 推广至多模式场景（AC 自动机）。

定理 3.1（KMP 自动机状态数最小性）：KMP 自动机的状态数 $|Q| = m+1$ 是识别模式 $P$ 所有出现的最小 DFA 状态数（在单模式精确匹配语义下）。

4. 理论推导

4.1 next 数组递推关系的推导

next 数组的构建依赖一个深刻的递推关系：$\text{next}[i]$ 可以基于 $\text{next}[i-1]$ 在均摊 $O(1)$ 时间内计算。

定理 4.1（next 数组递推）：设 $P$ 为模式串，$\text{next}$ 为按定义 3.6 约定的数组。定义 $\text{next}^{(1)}[i] = \text{next}[i]$，$\text{next}^{(k+1)}[i] = \text{next}[\text{next}^{(k)}[i]]$ 为 next 数组的迭代应用。则：

$\text{next}[i+1] = \begin{cases} \text{next}^{(k)}[i] + 1 & \text{若存在最小 } k \geq 1 \text{ 使得 } P[\text{next}^{(k)}[i]] = P[i] \\ -1 & \text{否则} \end{cases}$

证明思路：$\text{next}[i+1] = \text{lps}(P[0..i])$。由定义，$\text{lps}(P[0..i])$ 是 $P[0..i]$ 的最长相等前后缀长度。考虑两种情况：

1. 若 $P[\text{next}[i]] = P[i]$：则 $P[0.. \text{next}[i]]$ 是 $P[0..i]$ 的相等前后缀，长度为 $\text{next}[i]+1$。这是最长的，否则与 $\text{next}[i]$ 的定义矛盾
2. 若 $P[\text{next}[i]] \neq P[i]$：则 $P[0..i]$ 的相等前后缀必须比 $\text{next}[i]$ 短。设其为 $P[0..k-1]$（$k < \text{next}[i]$），则 $P[0..k-1]$ 也是 $P[0.. \text{next}[i]-1]$ 的相等前后缀（因 $P[i-k..i-1] = P[i-k..i-1]$，而 $P[0.. \text{next}[i]-1] = P[i-\text{next}[i]..i-1] \supseteq P[i-k..i-1]$）。故 $k = \text{next}^{(2)}[i] + 1$ 若 $P[\text{next}^{(2)}[i]] = P[i]$，否则继续递归

由此可得递推关系。$\blacksquare$

4.2 时间复杂度证明

定理 4.2（KMP 时间复杂度）：KMP 算法的预处理时间（BuildNext）为 $\Theta(m)$，匹配时间为 $\Theta(n)$，总时间为 $\Theta(n+m)$，空间为 $\Theta(m)$。

证明（摊还分析，势能法）：

BuildNext 阶段：

定义势能函数 $\Phi_i = j_i + 1$（构建 next 数组时的当前 $j$ 值，$+1$ 保证非负）。初始 $\Phi_0 = 0$，终止 $\Phi_m \geq 0$。

• 每次外层 for 循环 $i$ 增加 1，势能最多增加 1（因为 $j$ 最多增加 1）
• 每次 while 循环 $j$ 减少（$j \leftarrow \text{next}[j] < j$），势能至少减少 1

设外层循环共 $m-1$ 次，每次的实际代价为 $O(1) + \text{while 循环次数}$。while 循环的总次数受势能总减少量约束：

$\text{总 while 循环次数} \leq \Phi_0 + \text{总势能增加} = 0 + (m-1) = m-1$

故 BuildNext 总代价 $O(m)$。下界显然 $\Omega(m)$（必须读入 $P$），故 $\Theta(m)$。

Match 阶段：

定义势能函数 $\Phi_i = j_i + 1$（匹配时的当前 $j$ 值）。初始 $\Phi_0 = 0$，终止 $\Phi_n \geq 0$。

• 每次外层 for 循环 $i$ 增加 1，势能最多增加 1（$j$ 最多增加 1）
• 每次 while 循环 $j$ 减少，势能至少减少 1

类似地：

$\text{总 while 循环次数} \leq \Phi_0 + \text{总势能增加} = 0 + n = n$

故 Match 总代价 $O(n)$。下界显然 $\Omega(n)$（必须读入 $T$），故 $\Theta(n)$。

空间复杂度：next 数组 $O(m)$，其他变量 $O(1)$，总 $O(m)$。$\blacksquare$

4.3 正确性证明

定理 4.3（KMP 正确性）：KMP 算法输出的偏移集合 $\text{Output}$ 等于 $\text{Match}(T, P)$。

证明（基于不变式）：

不变式 4.1：在每次外层循环开始时（处理 $T[i]$ 之前），$j$ 满足：

$P[0..j-1] = T[i-j..i-1]$

即 $P$ 的前 $j$ 个字符等于 $T$ 中以 $i-1$ 结尾的 $j$ 个字符。$j=0$ 表示无已匹配前缀。

不变式 4.2：next 数组满足，对于任意 $j' = \text{next}[j]$：

$P[0..j'-1] = P[j-j'..j-1]$

即 $P[0..j'-1]$ 是 $P[0..j-1]$ 的最长相等前后缀。

初始性：循环开始前 $j = 0$，$P[0..-1] = \varepsilon = T[0..-1]$，不变式成立。

保持性：假设处理 $T[i-1]$ 后不变式 4.1 成立（$P[0..j-1] = T[i-j..i-1]$）。处理 $T[i]$ 时：

1. 若 $T[i] = P[j]$：则 $P[0..j] = T[i-j..i]$，不变式 4.1 对 $i+1$ 与 $j+1$ 成立
2. 若 $T[i] \neq P[j]$：执行 $j \leftarrow \text{next}[j]$。由不变式 4.2，$P[0.. \text{next}[j]-1] = P[j - \text{next}[j].. j-1]$。由不变式 4.1（在 $i$ 时刻），$P[j-\text{next}[j].. j-1] = T[i-\text{next}[j].. i-1]$。故 $P[0.. \text{next}[j]-1] = T[i-\text{next}[j].. i-1]$，即不变式 4.1 对 $i$ 与 $\text{next}[j]$ 成立。重复 while 循环直到 $T[i] = P[j']$ 或 $j' = -1$

终止性：当 $j = m$ 时，由不变式 4.1，$P[0..m-1] = T[i-m+1..i]$，即 $P = T[i-m+1..i]$，故 $s = i - m + 1$ 是匹配位置。算法输出 $s$ 后将 $j \leftarrow \text{next}[m-1]$，继续搜索下一个匹配，不遗漏任何匹配。

完备性：当 while 循环终止时，要么 $j = -1$（无前缀可匹配，$T[i]$ 不可能是任何 $P$ 前缀的延续），要么 $T[i] = P[j]$（找到最长相等前后缀）。next 数组保证 $j$ 跳转到最大的可能值，因此不会跳过任何可能的匹配。$\blacksquare$

4.4 字符比较次数的下界

定理 4.4（KMP 字符比较下界，Knuth-Morris-Pratt 1977）：在字母表 $\Sigma = \{a, b\}$ 上，任何基于”前缀匹配”的字符串匹配算法在最坏情况下至少需要 $2n - m$ 次字符比较。

证明思路（构造性下界）：取 $T = a^{n-m+1} b^{m-1}$，$P = a^{m-1} b$。算法必须确认 $P$ 在 $T$ 的位置 $n-m$ 处出现，且在前 $n-m$ 个位置不出现。

• 对于 $T$ 的前 $n-m+1$ 个字符 $a$，算法必须每个都至少比较一次以确认 $P$ 的前 $m-1$ 个 $a$ 已匹配
• 当算法在某个位置失配后，由于 $P$ 的前缀 $a^{m-1}$ 的最长相等前后缀是 $a^{m-2}$，next 数组使算法跳到 $a^{m-2}$ 继续比较，再失配跳到 $a^{m-3}$，…

完整证明见 Knuth-Morris-Pratt 1977 论文第 5 节。Cole 1994《Tight bounds on the complexity of the Boyer-Moore string matching algorithm》SIAM J. Comp. 23(5):1075-1091 将这一下界推广至更一般的算法类。

4.5 next 数组优化（nextval）的正确性

定义 4.1（nextval 数组）：nextval 数组是 next 数组的优化形式，定义为：

$\text{nextval}[j] = \begin{cases} \text{next}[j] & \text{若 } j = 0 \text{ 或 } P[j] \neq P[\text{next}[j]] \\ \text{nextval}[\text{next}[j]] & \text{若 } P[j] = P[\text{next}[j]] \end{cases}$

优化原理：若 $P[j] = P[\text{next}[j]]$，则当 $T[i] \neq P[j]$ 失配时，跳转到 $\text{next}[j]$ 后必然再次失配（因 $P[\text{next}[j]] = P[j] \neq T[i]$）。nextval 直接跳过这一必然失配的中间状态。

示例 3.3：$P = \text{"AAAAB"}$，next 与 nextval 对比：

解释：$\text{nextval}[1] = \text{nextval}[\text{next}[1]] = \text{nextval}[0] = -1$，因 $P[1] = P[\text{next}[1]] = P[0] = \text{A}$。

nextval 在不改变时间复杂度的前提下减少常数因子，是实际工程实现中的常用优化。

5. 代码示例

5.1 Python 实现（标准 KMP）

def build_next(pattern: str) -> list[int]:
    """
    构建 KMP 算法的 next 数组（约定 A，CLRS 风格）

    参数:
        pattern: 模式串 P[0..m-1]

    返回:
        next 数组，next[0] = -1（哨兵），next[i] = lps(P[0..i-1])

    时间复杂度: O(m)，基于势能法摊还分析
    空间复杂度: O(m)
    """
    m = len(pattern)
    if m == 0:
        return []
    next_arr = [-1] * m  # next[0] = -1 表示哨兵
    j = -1  # 当前已匹配的前缀长度
    for i in range(1, m):
        # 失配时沿 next 链回跳，直到匹配或到达哨兵
        while j >= 0 and pattern[i] != pattern[j + 1]:
            j = next_arr[j]
        # 当前字符匹配，扩展前缀长度
        if pattern[i] == pattern[j + 1]:
            j += 1
        next_arr[i] = j
    return next_arr


def kmp_search(text: str, pattern: str) -> list[int]:
    """
    KMP 字符串匹配，返回 pattern 在 text 中所有出现位置

    参数:
        text: 文本串 T[0..n-1]
        pattern: 模式串 P[0..m-1]

    返回:
        所有匹配偏移 s 的列表（升序）

    时间复杂度: O(n + m)
    空间复杂度: O(m)（next 数组）

    示例:
        >>> kmp_search("ABABDABACDABABCABAB", "ABABCABAB")
        [10]
        >>> kmp_search("AAAAA", "AA")
        [0, 1, 2, 3]
    """
    if not pattern:
        return []  # 空模式约定：无匹配
    n, m = len(text), len(pattern)
    if m > n:
        return []

    next_arr = build_next(pattern)
    j = -1  # 模式指针，初始为 -1（哨兵位置）
    matches = []

    for i in range(n):
        # 失配回跳
        while j >= 0 and text[i] != pattern[j + 1]:
            j = next_arr[j]
        # 当前字符匹配
        if text[i] == pattern[j + 1]:
            j += 1
        # 完整匹配
        if j == m - 1:
            matches.append(i - j)
            # 继续搜索下一个匹配：跳到 next[m-1]
            j = next_arr[j]

    return matches


# 演示
if __name__ == "__main__":
    text = "ABABDABACDABABCABAB"
    pattern = "ABABCABAB"
    print(f"text    = {text}")
    print(f"pattern = {pattern}")
    print(f"next    = {build_next(pattern)}")
    print(f"matches = {kmp_search(text, pattern)}")
    # 输出:
    # next    = [-1, -1, 0, 1, 2, -1, 0, 1, 2]
    # matches = [10]

5.2 Python 实现（nextval 优化版）

def build_nextval(pattern: str) -> list[int]:
    """
    构建 KMP 算法的优化 next 数组（nextval）

    nextval[j] 跳过"必然失配"的中间状态：
    若 P[j] = P[next[j]]，则 nextval[j] = nextval[next[j]]
    否则 nextval[j] = next[j]

    参数:
        pattern: 模式串

    返回:
        nextval 数组

    时间复杂度: O(m)
    空间复杂度: O(m)
    """
    m = len(pattern)
    if m == 0:
        return []
    next_arr = build_next(pattern)
    nextval = [-1] * m
    for j in range(1, m):
        if pattern[j] == pattern[next_arr[j]]:
            # P[j] 与 P[next[j]] 相等，失配后跳到 next[j] 必然再次失配
            nextval[j] = nextval[next_arr[j]]
        else:
            nextval[j] = next_arr[j]
    return nextval


# 测试 nextval
if __name__ == "__main__":
    pattern = "AAAAB"
    print(f"pattern   = {pattern}")
    print(f"next      = {build_next(pattern)}")
    print(f"nextval   = {build_nextval(pattern)}")
    # 输出:
    # next      = [-1, 0, 1, 2, 3]
    # nextval   = [-1, -1, -1, -1, 3]

5.3 C++ 实现（生产级）

#include <vector>
#include <string>
#include <iostream>

// 构建 KMP next 数组（约定 A，CLRS 风格）
// 时间复杂度 O(m)，空间复杂度 O(m)
std::vector<int> build_next(const std::string& pattern) {
    int m = pattern.size();
    if (m == 0) return {};
    std::vector<int> next_arr(m, -1);
    int j = -1;
    for (int i = 1; i < m; ++i) {
        // 失配回跳
        while (j >= 0 && pattern[i] != pattern[j + 1]) {
            j = next_arr[j];
        }
        // 当前字符匹配
        if (pattern[i] == pattern[j + 1]) {
            ++j;
        }
        next_arr[i] = j;
    }
    return next_arr;
}

// KMP 匹配，返回所有匹配偏移
// 时间复杂度 O(n + m)，空间复杂度 O(m)
std::vector<int> kmp_search(const std::string& text,
                            const std::string& pattern) {
    if (pattern.empty()) return {};
    int n = text.size(), m = pattern.size();
    if (m > n) return {};

    std::vector<int> next_arr = build_next(pattern);
    std::vector<int> matches;
    int j = -1;

    for (int i = 0; i < n; ++i) {
        while (j >= 0 && text[i] != pattern[j + 1]) {
            j = next_arr[j];
        }
        if (text[i] == pattern[j + 1]) {
            ++j;
        }
        if (j == m - 1) {
            matches.push_back(i - j);
            j = next_arr[j];  // 继续搜索下一个匹配
        }
    }
    return matches;
}

int main() {
    std::string text = "ABABDABACDABABCABAB";
    std::string pattern = "ABABCABAB";

    auto next_arr = build_next(pattern);
    std::cout << "next: ";
    for (int x : next_arr) std::cout << x << " ";
    std::cout << "\n";

    auto matches = kmp_search(text, pattern);
    std::cout << "matches: ";
    for (int s : matches) std::cout << s << " ";
    std::cout << "\n";
    // 输出:
    // next: -1 -1 0 1 2 -1 0 1 2
    // matches: 10
    return 0;
}

5.4 Java 实现（与 Sedgewick《Algorithms》4th 风格一致）

import java.util.ArrayList;
import java.util.List;

public class KMP {

    private final String pattern;
    private final int[] next;  // next 数组，约定 A

    /**
     * 构造 KMP 自动机，预编译模式串
     * 时间复杂度: O(m)，空间复杂度: O(m)
     */
    public KMP(String pattern) {
        this.pattern = pattern;
        int m = pattern.length();
        this.next = new int[m];
        buildNext();
    }

    /** 构建 next 数组（约定 A：next[0] = -1） */
    private void buildNext() {
        int m = pattern.length();
        if (m == 0) return;
        next[0] = -1;
        int j = -1;
        for (int i = 1; i < m; i++) {
            while (j >= 0 && pattern.charAt(i) != pattern.charAt(j + 1)) {
                j = next[j];
            }
            if (pattern.charAt(i) == pattern.charAt(j + 1)) {
                j++;
            }
            next[i] = j;
        }
    }

    /**
     * 在文本中搜索所有匹配位置
     * 时间复杂度: O(n)，空间复杂度: O(1)（不计 next 数组）
     */
    public List<Integer> search(String text) {
        List<Integer> matches = new ArrayList<>();
        if (pattern.isEmpty()) return matches;
        int n = text.length(), m = pattern.length();
        if (m > n) return matches;

        int j = -1;
        for (int i = 0; i < n; i++) {
            while (j >= 0 && text.charAt(i) != pattern.charAt(j + 1)) {
                j = next[j];
            }
            if (text.charAt(i) == pattern.charAt(j + 1)) {
                j++;
            }
            if (j == m - 1) {
                matches.add(i - j);
                j = next[j];  // 继续搜索
            }
        }
        return matches;
    }

    public static void main(String[] args) {
        KMP kmp = new KMP("ABABCABAB");
        List<Integer> matches = kmp.search("ABABDABACDABABCABAB");
        System.out.println("matches: " + matches);
        // 输出: matches: [10]
    }
}

5.5 KMP 自动机实现

class KMPAutomaton:
    """
    KMP 自动机：将 next 数组显式化为状态转移表

    状态 q 表示"已匹配 P 的前 q 个字符"
    转移 delta(q, c) 给出读入字符 c 后的新状态

    时间复杂度: 构建 O(m|Sigma|)，匹配 O(n)（摊还）
    空间复杂度: O(m|Sigma|)
    """

    def __init__(self, pattern: str, alphabet: str = "ABCD"):
        self.pattern = pattern
        self.alphabet = alphabet
        self.m = len(pattern)
        # 转移表 delta[q][c_index]
        self.delta = [[0] * len(alphabet) for _ in range(self.m + 1)]
        self._build()

    def _build(self):
        """构建状态转移表"""
        next_arr = build_next(self.pattern)
        # delta[0][c]：初始状态读入 c
        for ci, c in enumerate(self.alphabet):
            if c == self.pattern[0]:
                self.delta[0][ci] = 1
            else:
                self.delta[0][ci] = 0

        # 递推：delta[q][c] = delta[next[q]][c] 若 c != P[q]
        for q in range(1, self.m):
            for ci, c in enumerate(self.alphabet):
                if c == self.pattern[q]:
                    self.delta[q][ci] = q + 1
                else:
                    self.delta[q][ci] = self.delta[next_arr[q]][ci]

        # 接受状态 m：所有转移回 delta[next[m-1]][c]
        for ci, c in enumerate(self.alphabet):
            self.delta[self.m][ci] = self.delta[next_arr[self.m - 1]][ci]

    def search(self, text: str) -> list[int]:
        """匹配，返回所有出现位置"""
        q = 0  # 初始状态
        matches = []
        for i, c in enumerate(text):
            if c not in self.alphabet:
                q = 0
                continue
            ci = self.alphabet.index(c)
            q = self.delta[q][ci]
            if q == self.m:
                matches.append(i - self.m + 1)
        return matches


if __name__ == "__main__":
    auto = KMPAutomaton("ABABC", alphabet="ABC")
    print(auto.search("ABABABCAB"))  # 输出: [2]

5.6 应用扩展：最小循环节

KMP 的 next 数组还能用于求解字符串的最小循环节，这是 KMP 在字符串周期性问题中的经典应用。

定理 5.1（最小循环节）：设字符串 $S$ 长度为 $n$，$\pi[n-1]$ 为其前缀函数（即 $\text{PMT}[n-1]$）。则：

• 若 $n \bmod (n - \pi[n-1]) = 0$，则 $S$ 由长度为 $n - \pi[n-1]$ 的子串 $S[0..n-\pi[n-1]-1]$ 重复 $n / (n - \pi[n-1])$ 次构成
• 否则，$S$ 没有严格小于 $n$ 的循环节

def minimal_period(s: str) -> int:
    """
    求字符串 s 的最小循环节长度

    利用 KMP next 数组：若 n % (n - next[-1]) == 0，
    则最小循环节长度为 n - next[-1]，否则为 n

    时间复杂度: O(n)
    空间复杂度: O(n)
    """
    n = len(s)
    if n == 0:
        return 0
    # 计算前缀函数（PMT）
    pmt = [0] * n
    for i in range(1, n):
        j = pmt[i - 1]
        while j > 0 and s[i] != s[j]:
            j = pmt[j - 1]
        if s[i] == s[j]:
            j += 1
        pmt[i] = j

    period = n - pmt[n - 1]
    if n % period == 0:
        return period
    return n  # 无严格小于 n 的循环节


# 测试
if __name__ == "__main__":
    print(minimal_period("ABCABCABC"))  # 输出: 3
    print(minimal_period("ABABAB"))     # 输出: 2
    print(minimal_period("ABCDEF"))     # 输出: 6（无循环节）
    print(minimal_period("AAAAAA"))     # 输出: 1

5.7 应用扩展：字符串周期性判定

def is_periodic(s: str, k: int) -> bool:
    """
    判断字符串 s 是否以 k 为周期（即 s[i] = s[i % k]）

    利用 KMP 前缀函数：s 以 k 为周期 当且仅当
    n % k == 0 且 pmt[n-1] >= n - k

    时间复杂度: O(n)
    空间复杂度: O(n)
    """
    n = len(s)
    if n % k != 0:
        return False
    # 计算前缀函数
    pmt = [0] * n
    for i in range(1, n):
        j = pmt[i - 1]
        while j > 0 and s[i] != s[j]:
            j = pmt[j - 1]
        if s[i] == s[j]:
            j += 1
        pmt[i] = j
    return pmt[n - 1] >= n - k


# 测试
if __name__ == "__main__":
    print(is_periodic("ABCABCABC", 3))  # True
    print(is_periodic("ABCABCABC", 6))  # True
    print(is_periodic("ABCABCABC", 4))  # False

6. 对比分析

6.1 字符串匹配算法全景对比

其中 $w$ 为机器字长（通常 64），$k$ 为模式数。

6.2 KMP vs Boyer-Moore：范式之争

KMP 与 BM 几乎同期发表（1977），但范式截然不同：

实际工程中：GNU grep 优先使用 Boyer-Moore（在单模式场景），Linux 内核 strstr() 默认使用 KMP 变种（保证最坏线性）。Boyer-Moore 的实际优势来自坏字符跳跃：当文本中出现模式中不存在的字符时，可一次性跳过整段。

6.3 KMP vs Rabin-Karp：确定性 vs 随机化

6.4 KMP vs Aho-Corasick：单模式 vs 多模式

Aho-Corasick 是 KMP 在多模式场景的自然推广：将 next 数组替换为 trie 上的 failure link，使得失配时跳转到 trie 中”最长的、与当前已匹配后缀相同的前缀”。GNU grep -F（fixed strings）模式在多模式时使用 AC 算法。

6.5 KMP vs Suffix Array：模式预处理 vs 文本预处理

关键差异：KMP 适用于”短模式长文本、单次查询”场景；Suffix Array 适用于”长文本、多次模式查询”场景。在生物信息学中，参考基因组（数 GB）通常预构建 Suffix Array 或 FM-Index，测序 read（100bp）作为模式快速查询。

7. 常见陷阱

7.1 陷阱一：next 数组约定的混淆

:::danger 错误示例：混用约定 A（CLRS，next[0] = -1）与约定 B（国内教材，next[j] = lps - 1）

# 错误：构建时用约定 A，匹配时用约定 B 的跳转逻辑
def build_next_wrong(pattern):
    next_arr = [0] * len(pattern)  # 应该是 -1
    # ...

def kmp_wrong(text, pattern):
    next_arr = build_next_wrong(pattern)
    j = 0
    for i in range(len(text)):
        while j > 0 and text[i] != pattern[j]:
            j = next_arr[j - 1]  # 约定 B 的跳转，但 next_arr 是约定 A
        # ...

错误原因：约定 A 与约定 B 的跳转逻辑不同。约定 A 跳转 j = next[j]（next[j] 是 P[0..j-1] 的 lps），约定 B 跳转 j = next[j-1]（next[j-1] 是 P[0..j-1] 的 lps）。混用会导致漏匹配或越界。

修正方案：明确选用一种约定，构建与匹配逻辑保持一致。本文采用约定 A（CLRS 风格），next[0] = -1 为哨兵，跳转时 j = next[j]。

def build_next_correct(pattern):
    """约定 A：next[0] = -1，next[i] = lps(P[0..i-1])"""
    m = len(pattern)
    next_arr = [-1] * m  # 关键：next[0] = -1
    j = -1
    for i in range(1, m):
        while j >= 0 and pattern[i] != pattern[j + 1]:
            j = next_arr[j]
        if pattern[i] == pattern[j + 1]:
            j += 1
        next_arr[i] = j
    return next_arr


def kmp_correct(text, pattern):
    next_arr = build_next_correct(pattern)
    j = -1  # 匹配时也用约定 A
    matches = []
    for i in range(len(text)):
        while j >= 0 and text[i] != pattern[j + 1]:
            j = next_arr[j]  # 约定 A 跳转
        if text[i] == pattern[j + 1]:
            j += 1
        if j == len(pattern) - 1:
            matches.append(i - j)
            j = next_arr[j]
    return matches

:::

7.2 陷阱二：构建 next 数组时忘记哨兵

:::danger 错误示例：构建 next 数组时不设 -1 哨兵，导致越界或死循环

def build_next_no_sentinel(pattern):
    m = len(pattern)
    next_arr = [0] * m  # 错误：应该 next[0] = -1
    for i in range(1, m):
        j = next_arr[i - 1]
        while j > 0 and pattern[i] != pattern[j]:
            j = next_arr[j - 1]
        if pattern[i] == pattern[j]:
            j += 1
        next_arr[i] = j
    return next_arr

# 当 pattern 全部相同时（如 "AAAA"），next_arr = [0, 1, 2, 3]
# 匹配时 j 会无限回跳到自身，导致死循环