KMP 字符串匹配算法动态演示
算法简介
KMP（Knuth-Morris-Pratt）算法是一种高效的字符串匹配算法，由 Donald Knuth、James H. Morris 和 Vaughan Pratt 在1977年共同发明。
与朴素的字符串匹配算法相比，KMP 算法通过利用已经部分匹配这个有效信息，避免了主串指针的回溯。KMP 算法的核心在于预先计算一个 next 数组next[i] 存储模式串 P[0...i] 的最长相等前后缀的长度。这个长度值 `k` 意味着当 `P[i+1]` 与主串字符不匹配时，模式串可以向右滑动，使得 `P[k]` 对齐到当前主串字符，继续比较，而无需从头开始。 (有时也称为部分匹配表或失配函数)，该数组指导模式串在发生不匹配时应该向右滑动多少位，从而减少不必要的比较。
核心思想： 当主串中的字符 T[i] 与模式串中的字符 P[j] 不匹配时，不是简单地将模式串右移一位，而是根据 next[j-1] 的值，将模式串的指针 j 移动到 next[j-1]，相当于模式串向右滑动了 j - next[j-1] 位，然后继续比较 T[i] 和新的 P[j]。
时间复杂度分析
假设主串长度为 n，模式串长度为 m。
| 算法 | 预处理 (构建 next 数组) | 匹配过程 | 总体复杂度 |
|---|---|---|---|
| 暴力匹配 | O(1) | O(n×m) | O(n×m) |
| KMP 算法 | O(m) | O(n) | O(n+m) |
KMP 算法显著提高了匹配效率，尤其是在主串和模式串较长或重复字符较多时。
工作原理
KMP 算法包含两个主要阶段：
阶段一：构建 next 数组
此阶段的目标是计算模式串 `P` 的 `next` 数组。`next[i]` 表示子串 `P[0...i]` 的最长公共前缀和后缀 (Longest Proper Prefix which is also Suffix, LPS) 的长度。通过比较模式串自身的前缀和后缀来动态计算：
- 初始化 `next[0] = 0`。设置两个指针，`i` 从 1 开始遍历模式串，`j` (表示当前LPS的长度) 初始化为 0。
- 比较 `P[i]` 和 `P[j]`：
- 如果 `P[i] == P[j]`，说明找到了更长的LPS，则 `next[i] = j + 1`，然后 `i` 和 `j` 都递增。
- 如果 `P[i] != P[j]`：
- 若 `j > 0`，说明当前LPS (`P[0...j-1]`) 的下一个字符不匹配。我们需要在已知的LPS信息中寻找次长的LPS，使得它的下一个字符可能与 `P[i]` 匹配。这个信息就是 `next[j-1]`。所以令 `j = next[j-1]`，然后返回第2步重新比较 `P[i]` 和新的 `P[j]` (此时 `i` 不变)。
- 若 `j == 0`，说明在模式串的开头就没有匹配，LPS长度为0，则 `next[i] = 0`，然后 `i` 递增，`j` 保持为 0。
- 重复步骤 2 直到 `i` 遍历完整个模式串。
阶段二：匹配过程
利用计算好的 `next` 数组在主串 `T` 中查找模式串 `P`。设置两个指针，`i` 遍历主串 `T`，`j` 遍历模式串 `P`：
- 比较 `T[i]` 和 `P[j]`：
- 如果 `T[i] == P[j]`，说明当前字符匹配，则 `i` 和 `j` 都递增，继续比较下一对字符。
- 如果 `T[i] != P[j]`：
- 若 `j > 0`，说明发生了失配，但模式串已经匹配了 `j` 个字符 (`P[0...j-1]`)。根据 `next` 数组的定义，我们知道 `P[0...next[j-1]-1]` 是 `P[0...j-1]` 的最长公共前后缀。这意味着我们不需要将模式串完全移回开头，只需将模式串向右“滑动”，使得 `P` 的前 `next[j-1]` 个字符 (即 `P[0...next[j-1]-1]`) 对齐到 `T` 中刚刚比较过的 `j` 个字符的后 `next[j-1]` 个字符。这等效于将模式串指针 `j` 回溯到 `next[j-1]`。然后，保持 `i` 不变，返回第 1 步重新比较 `T[i]` 和新的 `P[j]`。
- 若 `j == 0`，说明模式串的第一个字符就与主串当前字符不匹配，那么只能将主串指针 `i` 递增，`j` 保持为 0，继续比较 `T[i+1]` 和 `P[0]`。
- 当 `j` 增加到等于模式串长度 `m` 时，说明找到了一个完整的匹配。记录下匹配的起始位置 (`i - m`)。为了查找后续可能的匹配，根据 `next[m-1]` 的值将 `j` 回溯 (`j = next[j-1]`)，然后继续步骤 1。
- 重复步骤 1 和 2 直到 `i` 遍历完整个主串 `T`。