KMP算法

快速概览

KMP算法通过预处理模式串构建failure function，在失配时避免无谓的重复比较，实现O(n+m)的线性时间复杂度，是字符串算法的经典范例。

• 核心思想：利用模式串自身的重复结构避免回退
• failure function π[i]：最长真前缀同时也是后缀的长度
• 时间复杂度：预处理O(m)，匹配O(n+m)，最坏情况保证
• 理论意义：证明字符串匹配可以在线性时间内完成

前置知识

所属板块 核心方法

索引、比对、组装与概率模型构成的核心算法主轴。

阅读目标 帮助建立阅读上下文

先判断这页与你当前问题的关系，再决定是否深入展开。

建议前置 先建立相关基础对象与方法直觉

建议先建立相关基础对象与方法直觉，再进入本页。

问题背景与动机

Knuth-Morris-Pratt（KMP）算法解决的是经典的精确字符串匹配问题：

给定文本 T 和模式串 P，在 T 中找出所有与 P 完全相同的出现位置。

与朴素扫描不同，KMP的关键创新是：当发生失配时，不是简单地回退到下一个位置重新开始，而是利用已经匹配过的信息，跳过那些肯定不会匹配的位置。

算法历史

KMP算法由 Donald Knuth、James H. Morris 和 Vaughan Pratt 于1977年发表，是首个在最坏情况下具有线性时间复杂度的字符串匹配算法。

发表背景：

• Morris 在 IBM 工作时独立发现了该算法（1970年）
• Knuth 和 Pratt 随后独立发现了类似结果
• 三人合作发表了经典论文 “Fast pattern matching in strings”

历史意义：

• 证明了字符串匹配可以在 $O(n+m)$ 时间内完成
• 开创了”预处理模式串以加速匹配”的算法范式
• failure function 的概念影响了后续众多算法

在生物信息学中的价值

虽然现代生物信息学工具很少直接使用KMP算法，但其核心思想具有深远影响：

算法思想传承：

• Aho-Corasick算法：将failure function扩展到多模式匹配场景
• Suffix Automaton：利用类似的重复结构进行高效字符串处理
• Read Mapper设计：seed-and-extend策略中避免重复计算的思想

教学价值：

• 理解”预处理如何避免重复计算”的经典案例
• 理解复杂度分析的实际意义
• 建立字符串算法的理论基础

局限性： KMP在生物信息学中的直接应用有限，主要因为：

• 实际生物序列查询通常需要近似匹配（允许错配）
• 大规模基因组查询更适合基于索引的方法（BWT/FM-index）
• 多模式匹配场景更常用Aho-Corasick

核心思想

朴素扫描的问题

考虑在文本 T = "ABABABAB..." 中匹配模式串 P = "ABABC"：

T: A B A B A B A B ...
P: A B A B C
      ^ 失配

朴素扫描会：

1. 从位置0开始，匹配到第4个字符时失配（C vs B）
2. 回退到位置1重新开始
3. 重复比较前面已经匹配过的”ABAB”

问题是：我们已经知道位置1-3是”ABA”，但朴素方法没有利用这个信息。

KMP的洞察

KMP的关键观察是：当在位置 i 失配时，我们已经知道 T[i-j:i] 与 P[0:j] 完全匹配。如果 P 的某个前缀同时也是这个匹配后缀的后缀，我们就可以利用这个信息跳过一些位置。

具体来说，如果 P[0:j] 的某个真前缀等于它的后缀，那么我们可以直接跳到下一个可能匹配的位置，而无需重新比较。

Failure Function

failure function `π[i]`

表示模式串 `P` 的前缀 `P[0:i]` 的最长真前缀同时也是该前缀后缀的长度。

真前缀

不等于整个字符串的前缀。

失配时跳转

当在位置 `i` 失配时，模式串跳转到 `π[i-1]` 位置继续比较。

数学定义

对于模式串 P = p_0p_1...p_{m-1}，定义 π[i] 为：

$$\pi[i] = \max\\{k < i \mid P[0:k] = P[i-k:i]\\}$$

即：P[0:i] 的最长真前缀同时也是该前缀后缀的长度。

计算failure function

算法1：计算failure function

输入：模式串 P = p_0p_1...p_\{m-1\}
输出：failure function π[0:m]

1. π[0] = 0
2. j = 0
3. for i = 1 to m-1:
   a. while j > 0 and P[i] ≠ P[j]:
      j = π[j-1]
   b. if P[i] == P[j]:
      j = j + 1
   c. π[i] = j
4. return π

时间复杂度：$O(m)$

空间复杂度：$O(m)$

示例

考虑模式串 P = "ABABC"：

i	P[i]	j (匹配长度)	π[i]
0	A	0	0
1	B	0 → 1	1
2	A	1 → 0 → 1	1
3	B	1 → 2	2
4	C	2 → 0	0

得到的failure function为：π = [0, 1, 1, 2, 0]

KMP匹配算法

算法2：KMP字符串匹配

输入：文本 T = t_0t_1...t_\{n-1\}，模式串 P = p_0p_1...p_\{m-1\}
输出：所有匹配位置

1. 预处理：计算failure function π
2. j = 0  // 模式串中的当前匹配位置
3. for i = 0 to n-1:
   a. while j > 0 and T[i] ≠ P[j]:
      j = π[j-1]  // 失配时跳转
   b. if T[i] == P[j]:
      j = j + 1
   c. if j == m:
      // 找到完整匹配
      输出匹配位置 i - m + 1
      j = π[j-1]  // 继续寻找下一个匹配

时间复杂度：$O(n + m)$

空间复杂度：$O(m)$

示例

在文本 T = "ABABABABC" 中匹配 P = "ABABC"：

T: A B A B A B A B C
P: A B A B C
   ^ 匹配 j=0→1

T: A B A B A B A B C
P:   A B A B C
     ^ 匹配 j=1→2

T: A B A B A B A B C
P:     A B A B C
       ^ 匹配 j=2→3

T: A B A B A B A B C
P:       A B A B C
         ^ 匹配 j=3→4

T: A B A B A B A B C
P:         A B A B C
           ^ 失配，j = π[3] = 2

T: A B A B A B A B C
P:         A B A B C
             ^ 失配，j = π[1] = 1

T: A B A B A B A B C
P:           A B A B C
               ^ 匹配 j=1→2

...继续...

最终在位置4找到匹配："ABABC"

复杂度分析

时间复杂度

• 预处理：计算failure function需要 $O(m)$ 时间
• 匹配：主循环中，文本指针 i 只向前移动，模式串指针 j 通过failure function跳转，总的比较次数不超过 $2n$
• 总体：$O(n + m)$

为什么是线性时间

关键在于：

• 文本指针 i 在外层循环中只增不减
• 模式串指针 j 通过failure function跳转，但每次跳转都会让 j 减小
• j 的总增加次数不超过 $n$，总减少次数也不超过 $n$
• 因此总操作次数是 $O(n)$

与其他算法的比较

算法	预处理时间	匹配时间	空间	特点
朴素扫描	$O(1)$	$O(mn)$	$O(1)$	简单但慢
KMP	$O(m)$	$O(n+m)$	$O(m)$	最坏情况线性，适合多次匹配同一模式
Boyer-Moore	$O(m+	\Sigma	)$	$O(n/m)$ 平均
Rabin-Karp	$O(m)$	$O(n+m)$ 平均	$O(1)$	哈希方法，适合多模式匹配

在生物信息学中的位置

KMP本身在现代生物信息学工具中不常直接使用，但：

• 思想传承：Aho-Corasick算法（多模式匹配）扩展了failure function的思想
• 索引基础：suffix automaton、suffix array等高级结构都利用了类似的预处理思想
• 教学价值：是理解”如何避免重复计算”的经典案例

在实际的生物序列搜索中，更常见的是：

• 基于k-mer的索引（如BWA、minimap2）
• 基于后缀的索引（如FM-index）
• 这些方法在预处理阶段构建复杂索引，查询时达到亚线性时间

常见误区

• KMP总是最快的：
• 不是。在实际应用中：
• Boyer-Moore在大多数情况下更快
• 基于索引的方法（如FM-index）在多次查询时优势明显
• KMP的价值在于理论保证和教学意义
• failure function就是模式串的重复结构：

历史注记

KMP算法的发表是字符串算法发展的重要里程碑。在此之前，人们认为字符串匹配的最坏时间复杂度不可能优于 $O(nm)$。KMP证明通过适当的预处理，线性时间是可以实现的。

有趣的是，Morris 在1970年就发现了该算法，但当时只作为 IBM 内部技术报告发布。直到1974年Knuth开始研究该问题，Morris 才公开发表自己的工作。Knuth、Morris 和 Pratt 最终合作完成了经典论文。

参考文献

1. Knuth, D. E., Morris, J. H., & Pratt, V. R. (1977). Fast pattern matching in strings. SIAM J. Comput., 6(2), 323-350.
2. Cormen, T. H., et al. (2009). Introduction to Algorithms (3rd ed.), Chapter 32. MIT Press.
3. Gusfield, D. (1997). Algorithms on Strings, Trees, and Sequences. Cambridge University Press.
4. Aho, A. V., & Corasick, M. J. (1975). Efficient string matching: an aid to bibliographic search. Commun. ACM, 18(6), 333-340.

相关页面

• 精确字符串匹配
• Trie与多模式匹配
• Boyer-Moore算法
• 索引结构概览

Boyer-Moore 算法

采用从右向左匹配策略的另一经典算法，实践中往往更快

延伸阅读

精确字符串匹配

字符串匹配问题的整体概览与算法分类

延伸阅读

Trie 与多模式匹配

KMP failure function 思想在多模式匹配中的扩展

延伸阅读

索引结构概览

现代生物序列搜索所依赖的索引技术总览

延伸阅读

哈希表

另一种高效查找数据结构，与 KMP 的预处理思想互补

延伸阅读