KMP算法基础：快速查找子串
在计算机科学中，字符串匹配是一个常见且重要的问题。我们经常需要在一段长文本（主串）中查找一个较短的字符串（模式串）是否存在，甚至找出它出现的所有位置。最直观的暴力匹配算法虽然简单，但效率低下，尤其是在处理大型文本时。为了解决这一问题，诞生了许多高效的算法，其中Knuth-Morris-Pratt (KMP) 算法就是一颗璀璨的明珠。
暴力匹配的困境
在深入KMP算法之前，我们先回顾一下暴力匹配（也称朴素匹配）的思路。它从主串的第一个字符开始，逐一与模式串的字符进行比较。如果匹配失败，主串的比较点向后移动一位，模式串重新从头开始比较。
例如，主串 S = "ABABDABACDABABCABAB"，模式串 P = "ABABCABAB"。
当发生不匹配时（例如 S[i] != P[j]），暴力算法会简单地将模式串向右移动一位，然后从头开始重新比较。这种方法的问题在于，当模式串与主串的部分前缀匹配成功，但最终失配时，暴力算法会丢弃所有已匹配的信息，重新开始比较，这导致了大量的冗余比较。在最坏情况下，其时间复杂度可达O(M*N)，其中M是主串长度，N是模式串长度。
KMP算法的核心思想：避免回溯
KMP算法的精髓在于，它利用了模式串本身的特性，在发生不匹配时，不是简单地将模式串向右移动一位，而是根据已经匹配过的信息，计算出模式串下一次应该对齐的位置，从而避免主串指针的回溯，提高了效率。
这一“不回溯”的机制，依赖于一个关键的数据结构：部分匹配表（Partial Match Table），也被称为LPS数组（Longest Proper Prefix which is also a Suffix）。
部分匹配表（LPS数组）
LPS数组为模式串的每一个前缀计算其“最长公共前后缀”的长度。更具体地说，对于模式串 P 的每一个前缀 P[0...i]，LPS数组的 lps[i] 值表示的是 P[0...i] 中最长的真前缀（Proper Prefix）同时也是真后缀（Proper Suffix）的长度。
- 真前缀：指除了字符串本身以外的所有前缀。
- 真后缀：指除了字符串本身以外的所有后缀。
我们以模式串 P = "ABABCABAB" 为例来构建LPS数组：
| 前缀 P[0…i] | 真前缀 | 真后缀 | 最长公共前后缀 | 长度 (lps[i]) |
|---|---|---|---|---|
| A | “” | “” | “” | 0 |
| AB | A | B | “” | 0 |
| ABA | A, AB | A, BA | A | 1 |
| ABAB | A, AB, ABA | B, AB, BAB | AB | 2 |
| ABABC | A, AB, ABA, ABAB | C, BC, ABC, BABC | “” | 0 |
| ABABCA | A, AB, … | A, CA, … | A | 1 |
| ABABCAB | A, AB, … | B, AB, … | AB | 2 |
| ABABCABA | A, AB, … | A, BA, … | ABA | 3 |
| ABABCABAB | A, AB, … | B, AB, … | ABAB | 4 |
所以，对于 P = "ABABCABAB"，其LPS数组为 [0, 0, 1, 2, 0, 1, 2, 3, 4]。
LPS数组的构建算法：
- 初始化
lps[0] = 0。 - 使用两个指针
len和i。len表示当前最长公共前后缀的长度，i用于遍历模式串。 - 如果
P[i]与P[len]相等，则len++，lps[i] = len，i++。 - 如果
P[i]与P[len]不相等：- 如果
len != 0，说明之前有匹配，将len回溯到lps[len-1]处，尝试更短的公共前后缀。 - 如果
len == 0，说明当前没有公共前后缀，lps[i] = 0，i++。
- 如果
KMP算法的匹配过程
有了LPS数组，KMP算法的匹配过程如下：
- 初始化两个指针：
i指向主串（文本）的当前字符，j指向模式串的当前字符。 - 当
S[i]与P[j]匹配时，i和j都向前移动一位。 - 如果
j达到了模式串的末尾（即j == N），则表示找到一个匹配项，记录匹配位置i - N。然后，为了寻找下一个匹配，我们将j更新为lps[j-1]，继续匹配。 - 如果
S[i]与P[j]不匹配：- 如果
j != 0，说明模式串的前缀已经匹配了一部分，此时根据LPS数组，将j更新为lps[j-1]。这意味着模式串向右移动，使得P[0...lps[j-1]-1]与S[i - lps[j-1] ... i-1]对齐。 - 如果
j == 0，说明模式串的第一个字符就与主串不匹配，此时主串指针i向前移动一位。
- 如果
示例 walkthrough
主串 S = "ABABDABACDABABCABAB"
模式串 P = "ABABCABAB"
LPS数组 lps = [0, 0, 1, 2, 0, 1, 2, 3, 4]
| S (i) | P (j) | 匹配状态 | 操作 | i | j | 备注 |
|---|---|---|---|---|---|---|
| A B A B D A B A C D A B A B C A B A B | A B A B C A B A B | S[0]=A, P[0]=A | 匹配，i++, j++ | 1 | 1 | |
| . A B A B D A B A C D A B A B C A B A B | . A B A B C A B A B | S[1]=B, P[1]=B | 匹配，i++, j++ | 2 | 2 | |
| . . A B D A B A C D A B A B C A B A B | . . A B C A B A B | S[2]=A, P[2]=A | 匹配，i++, j++ | 3 | 3 | |
| . . . B D A B A C D A B A B C A B A B | . . . B C A B A B | S[3]=B, P[3]=B | 匹配，i++, j++ | 4 | 4 | |
| . . . . D A B A C D A B A B C A B A B | . . . . C A B A B | S[4]=D, P[4]=C | 不匹配，j!=0, j=lps[j-1]=lps[3]=2 | 4 | 2 | P向右移动，利用”AB”的共同前后缀 |
| . . . . D A B A C D A B A B C A B A B | . . . . A B C A B A B | S[4]=D, P[2]=A | 不匹配，j!=0, j=lps[j-1]=lps[1]=0 | 4 | 0 | P继续向右移动 |
| . . . . D A B A C D A B A B C A B A B | A B A B C A B A B | S[4]=D, P[0]=A | 不匹配，j==0, i++ | 5 | 0 | S指针移动 |
| … | … | … | … | … | … | (省略一些步骤) |
| A B A B D A B A C D A B A B C A B A B | A B A B C A B A B | … | 匹配，j达到末尾 | 19 | 9 | 找到匹配项，位置为 i-N = 19-9 = 10 |
| … | … | j=lps[j-1]=lps[8]=4 | 19 | 4 | 继续查找下一个匹配 (如果存在) |
算法复杂度
- 时间复杂度：KMP算法在构建LPS数组阶段的时间复杂度为O(N)，在匹配阶段的时间复杂度为O(M)。因此，总时间复杂度为O(M+N)，这比暴力匹配的O(M*N)有了显著提升。
- 空间复杂度：KMP算法需要额外的空间来存储LPS数组，其大小与模式串的长度相同，即O(N)。
总结
KMP算法通过巧妙地利用模式串本身的结构信息（即部分匹配表），避免了在匹配失败时主串指针的回溯，从而实现了高效的字符串查找。它在文本编辑、生物信息学（如基因序列匹配）以及网络安全（如入侵检测系统）等领域都有广泛的应用。理解KMP算法不仅能够解决实际问题，也展示了算法设计中“利用已知信息，避免重复工作”的精妙思想。