KMP算法：字符串匹配的全面指南
Knuth-Morris-Pratt (KMP) 算法是一种高效的字符串匹配算法，它用于在一个文本串中搜索模式串的所有出现。与暴力匹配算法不同，KMP通过预处理步骤来避免不必要的比较，从而提高效率。在这篇博客中，我们将详细探讨KMP的工作原理、ne数组的构建过程，以及回退在算法中的关键作用。
目录
1. 字符串匹配介绍
字符串匹配是计算机科学中的一个常见问题，即需要在给定的文本串 s 中找到模式串 p 的所有出现。暴力匹配算法通过逐字符比较，但这种方法在面对长字符串时效率低下。KMP算法通过避免冗余比较来提高效率，而这一切都归功于 ne 数组（部分匹配表）的预处理。
2. KMP算法概述
KMP算法分为两个阶段：
- 预处理阶段：构建模式串
p的ne数组（部分匹配表）。 - 匹配阶段：利用
ne数组在文本s中搜索模式串p，当出现不匹配时，通过ne数组回退，避免重复比较。
关键概念：
ne数组：记录模式串中每个位置的最长相等前缀和后缀的长度。- 回退（Retreating）：当发生不匹配时，利用
ne数组让模式串回退到之前已经匹配的部分，而不是从头重新开始匹配。
3. ne数组（部分匹配表）
ne 数组是 KMP 算法的核心，它记录了模式串中每个位置最长相等前缀和后缀的长度。
假设模式串 p = "ABABC"，我们通过以下步骤构建 ne 数组：
逐步计算：
- 对于
p[1] = A，没有前缀或后缀，所以ne[1] = 0。 - 对于
p[2] = B，与p[1] = A不匹配，因此ne[2] = 0。 - 对于
p[3] = A，与p[1] = A匹配，因此ne[3] = 1。 - 对于
p[4] = B，与p[2] = B匹配，因此ne[4] = 2。 - 对于
p[5] = C，与p[3] = A不匹配，所以回退到ne[4]，最终ne[5] = 0。
最终的 ne 数组为 [0, 0, 1, 2, 0]。
4. 逐步示例
示例：
让我们通过一个具体的例子来演示如何计算 ne 数组，对于模式串 p = "ABABC"：
- 从
i = 2开始，比较p[2] = B和p[1] = A→ 不匹配，所以ne[2] = 0。 - 移动到
i = 3，比较p[3] = A和p[1] = A→ 匹配，所以ne[3] = 1。 - 移动到
i = 4，比较p[4] = B和p[2] = B→ 匹配，所以ne[4] = 2。 - 在
i = 5时，比较p[5] = C和p[3] = A→ 不匹配。因此我们使用ne[4] = 2回退，比较p[5] = C和p[2] = B→ 仍不匹配，所以ne[5] = 0。
这显示了如何通过回退避免从头开始匹配。
5. get_next函数：构建ne数组
get_next 函数用于构建 ne 数组。以下是函数代码及其解释：
void get_next() {
for (int i = 2, j = 0; i <= n; i++) { // 从模式串的第2个字符开始
while (j && p[i] != p[j + 1]) j = ne[j]; // 当字符不匹配时，回退j
if (p[i] == p[j + 1]) j++; // 如果匹配成功，j前进
ne[i] = j; // 存储当前i位置的最长相等前后缀长度
}
}解释：
i从模式串的第二个字符开始遍历。- 当
p[i] != p[j + 1]时，使用ne[j]回退j。 - 当匹配成功时，
j增加，并更新ne[i]的值。 - 该过程会一直持续到构建完整的
ne数组。
6. KMP匹配过程
一旦我们构建了 ne 数组，KMP的匹配过程就可以高效地进行。具体步骤如下：
- 我们将模式串
p与文本s进行比较。 - 如果字符匹配，两个指针（
i用于文本，j用于模式串）同时前进。 - 如果出现不匹配，使用
ne数组回退j，而不需要重新设置i。
void kmp() {
for (int i = 1, j = 0; i <= m; i++) { // 遍历主串
while (j && s[i] != p[j + 1]) j = ne[j]; // 当不匹配时，回退 j
if (s[i] == p[j + 1]) j++; // 如果匹配，继续前进
if (j == n) { // 如果模式串全部匹配完成
printf("%d ", i - n); // 输出匹配起始位置
j = ne[j]; // 回退 j，寻找下一个可能的匹配
}
}
}关键点：
- 当发生不匹配时，我们通过
ne数组回退j，避免从头开始匹配。 - 与暴力匹配相比，这种方法显著提升了效率。
7. 回退示例
让我们使用文本 s = "ABABDABACDABABC" 和模式串 p = "ABABC" 来展示回退的实际操作：
- 开始时，
s[1] = A和p[1] = A匹配。 - 继续匹配
s[2] = B和p[2] = B，匹配成功。 - 直到
s[5] = D和p[5] = C不匹配。 - 通过
ne[4] = 2，我们回退到p[3] = A，然后与s[5] = D比较，仍然不匹配。 - 最终回退到
ne[2] = 0，重新从p[1]开始。
这一过程展示了如何利用回退机制避免不必要的比较。
8. 总结
KMP算法是一种高效的字符串匹配算法，通过预处理 ne 数组，在匹配过程中避免从头重新比较。ne 数组帮助记录最长相等前后缀的长度，回退的使用大大提升了匹配效率。
通过对 ne 数组的理解和使用，KMP算法能够极大提高字符串匹配的效率。希望本篇博客能够帮助你掌握KMP算法的核心思想并能够应用到实际项目中。