KMP 算法教程：高效字符串匹配

在计算机科学中，字符串匹配是一个常见且重要的问题。我们经常需要在一段长文本中查找某个特定的模式字符串。最直观的暴力匹配算法虽然简单，但在最坏情况下效率低下。为了解决这个问题，Donald Knuth、Vaughan Pratt 和 James Morris 共同提出了著名的 KMP (Knuth-Morris-Pratt) 算法，它通过巧妙地预处理模式字符串，实现了高效的字符串匹配。

暴力匹配的局限性

首先，让我们回顾一下暴力匹配算法。当在文本 T 中查找模式 P 时，暴力匹配会从文本的起始位置开始，逐个字符地比较 T 和 P。如果遇到不匹配，它会将模式 P 向右移动一位，然后从头开始重新比较。

例如：
文本 T = "ABABDABACDABABCABAB"
模式 P = "ABABCABAB"

在匹配过程中，如果 T[i] 和 P[j] 不匹配，暴力算法会简单地将 P 向右移动一位，然后从 T[i-j+1] 处重新开始比较 P[0]。这种方法的问题在于，当发生不匹配时，它会丢弃已经比较过的信息，导致大量的重复比较，尤其是在模式中存在重复子串的情况下。其最坏时间复杂度可达 O(n*m)，其中 n 是文本长度，m 是模式长度。

KMP 算法的核心思想：避免回溯

KMP 算法的精髓在于，当发生不匹配时，它不会简单地将模式向右移动一位，而是利用模式字符串自身的特点，计算出模式应该向前“跳跃”多少位，从而避免文本指针 i 的回溯。这意味着文本中的每一个字符最多只会被比较一次，大大提高了效率。KMP 算法的时间复杂度为 O(n + m)，远优于暴力匹配。

实现这一高效跳跃的关键是构建一个名为 “最长公共前后缀” (Longest Proper Prefix which is also a Suffix, LPS) 数组，有时也称为“失配函数”或“部分匹配表”。

LPS 数组：KMP 算法的“加速器”

LPS 数组 lps[] 存储了模式字符串中每个位置的“部分匹配”信息。对于模式 P 中的每一个位置 i，lps[i] 的值表示子模式 P[0...i] 的最长“真前缀”的长度，该真前缀同时也是 P[0...i] 的“真后缀”。

前缀： 从字符串开头到某个位置的子串。
后缀： 从某个位置到字符串结尾的子串。
真前缀/真后缀： 不包括字符串本身的非空前缀/后缀。

当模式 P 中的字符 P[j] 与文本 T 中的字符 T[i] 发生不匹配时，lps[j-1]（即已匹配部分 P[0...j-1] 的最长公共前后缀长度）会告诉我们模式应该如何移动。具体来说，模式 P 将移动到新的位置，使得 P[lps[j-1]] 对齐 T[i]，这样我们就可以继续从 P[lps[j-1]] 和 T[i] 处进行比较。

构建 LPS 数组（预处理模式字符串）

构建 LPS 数组是 KMP 算法的第一步，也是对模式字符串的预处理过程。我们使用两个指针 len 和 i 来遍历模式字符串。

LPS 数组构建算法步骤：

初始化一个与模式字符串长度相同的 lps 数组，所有元素置为 0。
lps[0] 始终为 0，因为单个字符没有真前缀或真后缀。
设置 len = 0 (表示当前找到的最长公共前后缀的长度)。
设置 i = 1 (从模式的第二个字符开始遍历)。
循环直到 i 达到模式字符串的末尾：
- 如果 pattern[i] == pattern[len]：
  - len 增加 1。
  - lps[i] 设置为 len。
  - i 增加 1。
- 否则 (pattern[i] != pattern[len])：
  - 如果 len != 0：
    - len 更新为 lps[len - 1]。这表示我们需要寻找一个更短的公共前后缀。
  - 否则 (len == 0)：
    - lps[i] 设置为 0。
    - i 增加 1。

示例：构建模式 P = "ABABAC" 的 LPS 数组

Index (i)	Character (`P[i]`)	`len` (当前长度)	`P[i]` vs `P[len]`	动作	`lps` 数组 (更新后)
0	A	–	–	`lps[0] = 0`	`[0, 0, 0, 0, 0, 0]`
1	B	0	`P[1]`(B) != `P[0]`(A)	`len` 为 0，`lps[1] = 0`，`i++`	`[0, 0, 0, 0, 0, 0]`
2	A	0	`P[2]`(A) == `P[0]`(A)	`len` 变为 1，`lps[2] = 1`，`i++`	`[0, 0, 1, 0, 0, 0]`
3	B	1	`P[3]`(B) == `P[1]`(B)	`len` 变为 2，`lps[3] = 2`，`i++`	`[0, 0, 1, 2, 0, 0]`
4	A	2	`P[4]`(A) == `P[2]`(A)	`len` 变为 3，`lps[4] = 3`，`i++`	`[0, 0, 1, 2, 3, 0]`
5	C	3	`P[5]`(C) != `P[3]`(B)	`len` 更新为 `lps[len-1]` (`lps[2] = 1`)，`len` 变为 1	`[0, 0, 1, 2, 3, 0]`
5	C	1	`P[5]`(C) != `P[1]`(B)	`len` 更新为 `lps[len-1]` (`lps[0] = 0`)，`len` 变为 0	`[0, 0, 1, 2, 3, 0]`
5	C	0	`len` 为 0，`lps[5] = 0`，`i++`	`[0, 0, 1, 2, 3, 0]`

最终，模式 P = "ABABAC" 的 LPS 数组为 [0, 0, 1, 2, 3, 0]。

KMP 匹配算法

在 LPS 数组构建完成后，KMP 匹配算法的主体部分也使用两个指针：

i：指向文本 T 的当前字符。
j：指向模式 P 的当前字符。

KMP 匹配算法步骤：

初始化 i = 0，j = 0。
循环直到 i 达到文本 T 的末尾：
- 如果 pattern[j] == text[i]：
  - i 增加 1。
  - j 增加 1。
- 如果 j 达到了模式 P 的长度 (j == m)：
  - 找到了一个匹配！记录匹配的起始位置 (i - j)。
  - 为了寻找下一个可能的匹配，更新 j 为 lps[j - 1]。
- 否则 (pattern[j] != text[i])：
  - 如果 j != 0：
    - j 更新为 lps[j - 1]。模式向右“跳跃”。
  - 否则 (j == 0)：
    - i 增加 1。模式的第一个字符都不匹配，文本指针向前移动。

总结

KMP 算法通过预处理模式字符串，构建 LPS 数组，从而在发生不匹配时，能够高效地移动模式，避免文本指针的回溯。这种机制使得 KMP 算法在字符串匹配问题上具有出色的时间效率，是面试和实际开发中都非常重要的算法之一。掌握 KMP 算法不仅能解决字符串匹配问题，其思想也对理解其他高效算法有所启发。