KMP算法：字符串匹配的全面指南

Knuth-Morris-Pratt (KMP) 算法是一种高效的字符串匹配算法，它用于在一个文本串中搜索模式串的所有出现。与暴力匹配算法不同，KMP通过预处理步骤来避免不必要的比较，从而提高效率。在这篇博客中，我们将详细探讨KMP的工作原理、ne数组的构建过程，以及回退在算法中的关键作用。

---

目录

1. 字符串匹配介绍
2. KMP算法概述
3. ne数组（部分匹配表）
4. 逐步示例
5. get_next函数：构建ne数组
6. KMP匹配过程
7. 回退示例
8. 总结

---

1. 字符串匹配介绍

字符串匹配是计算机科学中的一个常见问题，即需要在给定的文本串 s 中找到模式串 p 的所有出现。暴力匹配算法通过逐字符比较，但这种方法在面对长字符串时效率低下。KMP算法通过避免冗余比较来提高效率，而这一切都归功于 ne 数组（部分匹配表）的预处理。

---

2. KMP算法概述

KMP算法分为两个阶段：

1. 预处理阶段：构建模式串 p 的 ne 数组（部分匹配表）。
2. 匹配阶段：利用 ne 数组在文本 s 中搜索模式串 p，当出现不匹配时，通过 ne 数组回退，避免重复比较。

关键概念：

• ne 数组：记录模式串中每个位置的最长相等前缀和后缀的长度。
• 回退（Retreating）：当发生不匹配时，利用 ne 数组让模式串回退到之前已经匹配的部分，而不是从头重新开始匹配。

---

3. ne数组（部分匹配表）

ne 数组是 KMP 算法的核心，它记录了模式串中每个位置最长相等前缀和后缀的长度。

假设模式串 p = "ABABC"，我们通过以下步骤构建 ne 数组：

逐步计算：

1. 对于 p[1] = A，没有前缀或后缀，所以 ne[1] = 0。
2. 对于 p[2] = B，与 p[1] = A 不匹配，因此 ne[2] = 0。
3. 对于 p[3] = A，与 p[1] = A 匹配，因此 ne[3] = 1。
4. 对于 p[4] = B，与 p[2] = B 匹配，因此 ne[4] = 2。
5. 对于 p[5] = C，与 p[3] = A 不匹配，所以回退到 ne[4]，最终 ne[5] = 0。

最终的 ne 数组为 [0, 0, 1, 2, 0]。

---

4. 逐步示例

示例：

让我们通过一个具体的例子来演示如何计算 ne 数组，对于模式串 p = "ABABC"：

1. 从 i = 2 开始，比较 p[2] = B 和 p[1] = A → 不匹配，所以 ne[2] = 0。
2. 移动到 i = 3，比较 p[3] = A 和 p[1] = A → 匹配，所以 ne[3] = 1。
3. 移动到 i = 4，比较 p[4] = B 和 p[2] = B → 匹配，所以 ne[4] = 2。
4. 在 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的匹配过程就可以高效地进行。具体步骤如下：

1. 我们将模式串 p 与文本 s 进行比较。
2. 如果字符匹配，两个指针（i 用于文本，j 用于模式串）同时前进。
3. 如果出现不匹配，使用 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" 来展示回退的实际操作：

1. 开始时，s[1] = A 和 p[1] = A 匹配。
2. 继续匹配 s[2] = B 和 p[2] = B，匹配成功。
3. 直到 s[5] = D 和 p[5] = C 不匹配。
4. 通过 ne[4] = 2，我们回退到 p[3] = A，然后与 s[5] = D 比较，仍然不匹配。
5. 最终回退到 ne[2] = 0，重新从 p[1] 开始。

这一过程展示了如何利用回退机制避免不必要的比较。

---

8. 总结

KMP算法是一种高效的字符串匹配算法，通过预处理 ne 数组，在匹配过程中避免从头重新比较。ne 数组帮助记录最长相等前后缀的长度，回退的使用大大提升了匹配效率。

---

通过对 ne 数组的理解和使用，KMP算法能够极大提高字符串匹配的效率。希望本篇博客能够帮助你掌握KMP算法的核心思想并能够应用到实际项目中。