KMP字符串匹配算法教程：概念、实例与优化
摘要
KMP (Knuth-Morris-Pratt) 字符串匹配算法是一种高效的字符串搜索算法，旨在解决在一个长文本中查找一个模式串出现位置的问题。与传统的朴素字符串匹配算法相比，KMP 算法通过避免不必要的字符比较，显著提升了匹配效率，其最坏情况时间复杂度为 O(n + m)，其中 ‘n’ 是文本长度，’m’ 是模式串长度。本文将详细介绍 KMP 算法的核心概念、LPS (Longest Proper Prefix which is also Suffix) 数组的构建与应用，并通过实例解析其工作原理，最后探讨其时间和空间复杂度。
1. 朴素字符串匹配算法的局限性
在深入 KMP 之前，我们先简要回顾朴素字符串匹配算法。朴素算法从文本的第一个字符开始，逐个比较模式串与文本中相应位置的字符。如果所有字符都匹配，则找到一个匹配；如果出现不匹配，模式串会向右移动一个位置，然后重新从头开始比较。
示例：
文本 (T): ABCABAABABC
模式 (P): ABABC
ABCABvsABABC-> 匹配到ABABA，第5个字符B与C不匹配。- 模式串右移一位。
BCABAvsABABC-> 第一个字符B与A不匹配。- 模式串右移一位。
这种方法的问题在于，当发生不匹配时，模式串只向右移动一位，很多文本中已经比较过的字符会被重复比较，导致在最坏情况下（例如文本为 AAAAA...，模式为 AAAB）时间复杂度高达 O(n * m)。KMP 算法的诞生正是为了克服这一局限性。
2. KMP 算法的核心概念
KMP 算法的核心思想是，当模式串与文本发生不匹配时，它利用已匹配部分的信息，避免将模式串仅仅向右移动一位，而是根据预处理的模式串信息，进行“跳跃式”的移动，从而减少比较次数。这主要依赖于以下概念：
2.1 前缀与后缀
- 前缀 (Prefix)：一个字符串从开头开始的子串。例如，字符串 “ABC” 的前缀有 “”, “A”, “AB”, “ABC”。
- 后缀 (Suffix)：一个字符串从末尾结束的子串。例如，字符串 “ABC” 的后缀有 “”, “C”, “BC”, “ABC”。
- 真前缀 (Proper Prefix) 或 真后缀 (Proper Suffix)：除了字符串本身之外的所有前缀或后缀。例如，”ABC” 的真前缀有 “”, “A”, “AB”。
2.2 LPS 数组（最长公共前后缀数组 / 部分匹配表 / 失配函数）
LPS 数组是 KMP 算法的灵魂。它是一个与模式串等长的数组，LPS[i] 存储的是模式串 P[0...i] 的最长真前缀的长度，且该真前缀同时也是 P[0...i] 的真后缀。
LPS 数组的作用： 当模式串的 j 位置与文本的 i 位置发生不匹配时，LPS[j-1] 的值告诉我们模式串应该如何“回溯”，也就是将模式串向右移动多少位，以便将模式串中 P[0...LPS[j-1]-1] 这一段已经匹配的子串对齐到文本中，从而避免从模式串的开头重新开始比较，节省时间。
示例：构建模式串 “ABABC” 的 LPS 数组
| 索引 (i) | 字符 (P[i]) | 前缀 P[0...i] |
真前缀 | 真后缀 | 最长公共前后缀长度 (LPS[i]) |
|---|---|---|---|---|---|
| 0 | A | A | “” | “” | 0 |
| 1 | B | AB | A | B | 0 |
| 2 | A | ABA | A, AB | A, BA | 1 (“A”) |
| 3 | B | ABAB | A, AB, ABA | B, AB, BAB | 2 (“AB”) |
| 4 | C | ABABC | A, AB, ABA, ABAB | C, BC, ABC, BABC | 0 |
因此，模式串 “ABABC” 的 LPS 数组为 [0, 0, 1, 2, 0]。
LPS 数组的构建算法：
我们可以使用双指针法来构建 LPS 数组：
* len: 记录当前已知的最长公共前后缀的长度。
* i: 遍历模式串的指针，从 1 开始。
- 初始化
LPS[0] = 0，len = 0，i = 1。 - 当
i < m(模式串长度) 时循环：- 如果
P[i] == P[len]：表示当前字符匹配，len增加 1，LPS[i] = len，然后i增加 1。 - 如果
P[i] != P[len]：- 如果
len != 0：表示不能通过延长当前公共前后缀来匹配，我们需要尝试更短的公共前后缀。将len更新为LPS[len - 1]。 - 如果
len == 0：表示没有更短的公共前后缀可以匹配了，LPS[i] = 0，i增加 1。
- 如果
- 如果
3. KMP 匹配算法步骤
KMP 算法分为两个阶段：预处理模式串（构建 LPS 数组）和在文本中进行匹配。
匹配阶段：
使用两个指针：
* i：文本指针，从 0 开始。
* j：模式串指针，从 0 开始。
- 当
i < n(文本长度) 时循环：- 如果
T[i] == P[j]：当前字符匹配，i和j都增加 1。 - 如果
j == m(模式串长度)：表示找到一个匹配，匹配起始位置是i - j。为了查找下一个匹配，我们将j更新为LPS[j-1]。 - 如果
T[i] != P[j]：- 如果
j != 0：表示模式串不是从头开始不匹配，利用 LPS 数组进行“回溯”，将j更新为LPS[j-1]。 - 如果
j == 0：表示模式串的第一个字符就不匹配，文本指针i增加 1。
- 如果
- 如果
示例：在文本 “ABABCABABABC” 中匹配模式串 “ABABC”
模式串 “ABABC” 的 LPS 数组为 [0, 0, 1, 2, 0]。
| 步骤 | 文本 (T) | 模式 (P) | i |
j |
比较 | 结果 | 操作 |
|---|---|---|---|---|---|---|---|
| 1 | ABABCABABABC |
ABABC |
0 | 0 | T[0]==P[0] | 匹配 | i++, j++ (i=1, j=1) |
| 2 | ABABCABABABC |
ABABC |
1 | 1 | T[1]==P[1] | 匹配 | i++, j++ (i=2, j=2) |
| 3 | ABABCABABABC |
ABABC |
2 | 2 | T[2]==P[2] | 匹配 | i++, j++ (i=3, j=3) |
| 4 | ABABCABABABC |
ABABC |
3 | 3 | T[3]==P[3] | 匹配 | i++, j++ (i=4, j=4) |
| 5 | ABABCABABABC |
ABABC |
4 | 4 | T[4]==P[4] | 匹配 | i++, j++ (i=5, j=5) |
| 6 | ABABCABABABC | ABABC | 5 | 5 | j == m (5) | 找到匹配! | 匹配位置：i-j = 5-5 = 0; j = LPS[j-1] = LPS[4] = 0. (i=5, j=0) |
| 7 | ABABCABABABC |
ABABC |
5 | 0 | T[5]==P[0] | 匹配 | i++, j++ (i=6, j=1) |
| 8 | ABABCABABABC |
ABABC |
6 | 1 | T[6]==P[1] | 匹配 | i++, j++ (i=7, j=2) |
| 9 | ABCABABABC |
ABABC |
7 | 2 | T[7]==P[2] | 匹配 | i++, j++ (i=8, j=3) |
| 10 | ABCABABABC |
ABABC |
8 | 3 | T[8]==P[3] | 匹配 | i++, j++ (i=9, j=4) |
| 11 | ABCABABABC |
ABABC |
9 | 4 | T[9]!=P[4] | 不匹配 | j != 0, j = LPS[j-1] = LPS[3] = 2. (i=9, j=2) |
| 12 | ABCABABABC |
ABABC |
9 | 2 | T[9]==P[2] | 匹配 | i++, j++ (i=10, j=3) |
| 13 | ABCABABCABC |
ABABC |
10 | 3 | T[10]==P[3] | 匹配 | i++, j++ (i=11, j=4) |
| 14 | ABCABABCABC |
ABABC |
11 | 4 | T[11]==P[4] | 匹配 | i++, j++ (i=12, j=5) |
| 15 | ABCABABCABC |
ABABC | 12 | 5 | j == m (5) | 找到匹配! | 匹配位置：i-j = 12-5 = 7; j = LPS[j-1] = LPS[4] = 0. (i=12, j=0) |
| 16 | end of text | 12 | 0 | – | 结束 |
最终找到两个匹配，起始索引分别为 0 和 7。
4. 优化：KMP 算法的性能分析
KMP 算法本身就是对朴素算法的重大优化。它的优化体现在以下几个方面：
4.1 时间复杂度
- LPS 数组构建： 构建 LPS 数组的过程是一个线性的过程。
i指针从 1 遍历到m-1，len指针最多递增m次，递减操作的总次数也不会超过m次。因此，构建 LPS 数组的时间复杂度为 O(m)。 - 匹配过程： 在文本中匹配模式串时，文本指针
i只会单向前进，最多移动n次。模式串指针j最多递增n次，每次回溯（j = LPS[j-1]）操作也会减少j的值，但j的总减少量不会超过j的总增加量。因此，匹配过程的时间复杂度为 O(n)。 - 总时间复杂度： 综上所述，KMP 算法的总时间复杂度为 O(n + m)，这比朴素算法的 O(n * m) 有显著提升，尤其是当模式串较长或文本中包含许多重复字符时。
4.2 空间复杂度
KMP 算法需要额外的空间来存储 LPS 数组。LPS 数组的大小与模式串的长度 m 相同。因此，KMP 算法的空间复杂度为 O(m)。
4.3 不回溯文本指针
KMP 算法的一个关键特性是，它在匹配过程中从不回溯文本指针 i。这保证了对文本的单向扫描，是其高效性的重要原因。当发生不匹配时，算法只会调整模式串指针 j，利用 LPS 数组的知识进行“智能”的模式串位移。
4.4 进一步的优化（理论层面）
虽然 KMP 已经非常高效，但有时会提及一些理论上的微调，例如在特定情况下，如果 P[j] 不匹配，并且 P[LPS[j-1]] 和 P[j] 相同，那么可以直接跳过这个 LPS[j-1] 的位置，直接去看 LPS[LPS[j-1]]。然而，这些微优化通常只会带来常数级的改进，并且会增加算法的实现复杂性，因此在实际应用中 KMP 的标准实现已经足够高效。
需要注意的是，像 Boyer-Moore 这样的算法在某些情况下（例如模式串和字母表都较大）在实践中可能会比 KMP 更快，因为它通常会跳过更多的文本字符。但 Boyer-Moore 的最坏情况复杂度仍可能达到 O(n * m)，而 KMP 始终保持 O(n + m)。
5. KMP 算法的应用
KMP 算法因其高效性，在计算机科学领域有广泛的应用：
- 文本编辑器和搜索引擎： 高效查找文档中的关键词或短语。
- 生物信息学： DNA 序列比对和分析，查找特定的基因序列。
- 网络入侵检测系统： 匹配网络流量中的恶意模式。
- 代码分析工具： 在源代码中查找特定的代码模式。
- 数据压缩： 某些压缩算法会利用字符串重复模式。
- 拼写检查器： 辅助识别和修正拼写错误。
结论
KMP 字符串匹配算法是计算机科学中一个经典的算法，它以其线性的时间复杂度在字符串匹配问题中占据重要地位。通过巧妙地利用模式串自身的结构信息（LPS 数组），KMP 算法在不回溯文本指针的前提下，实现了高效的匹配。理解其核心概念、LPS 数组的构建和匹配过程是掌握 KMP 算法的关键，这不仅有助于解决实际问题，也为更复杂的模式匹配算法奠定了基础。