字符串算法之KMP 算法（Knuth-Morris-Pratt Algorithm, 字符串匹配）详细解读

KMP算法（Knuth-Morris-Pratt Algorithm） 是一种高效的字符串匹配算法，用于在一个文本串中查找一个模式串的位置。它通过预处理模式串，减少了不必要的比较次数，从而提高了匹配效率。KMP算法的时间复杂度为 O(n+m)，其中 n 是文本串的长度，m 是模式串的长度。

KMP算法的基本原理

KMP算法的核心思想是使用已匹配的部分信息来避免重复比较。在匹配过程中，如果出现不匹配，KMP算法不会重新从头开始比较，而是利用一个部分匹配表（或称为“前缀表”）来决定从哪个位置重新开始匹配。

部分匹配表（前缀表）

部分匹配表（pi数组）是一个数组，其中的每个元素 pi[i] 表示模式串中，前 i 个字符的最长相等前后缀的长度。这个表的作用是在出现不匹配时，帮助我们跳过已匹配的部分，直接从合适的位置继续比较。

例如，对于模式串 "ABABCABAB"，其前缀表如下：

A：前缀 ""，后缀 ""，长度为 0。
AB：前缀 "A"，后缀 ""，长度为 0。
ABA：前缀 "A"，后缀 "A"，长度为 1。
ABAB：前缀 "AB"，后缀 "AB"，长度为 2。
ABABC：前缀 "ABAB"，后缀 "A"，长度为 0。
ABABCA：前缀 "ABABC"，后缀 "AB"，长度为 2。
ABABCAB：前缀 "ABABCA"，后缀 "ABAB"，长度为 3。
ABABCABA：前缀 "ABABCAB"，后缀 "AB"，长度为 2。
ABABCABAB：前缀 "ABABCABA"，后缀 "ABAB"，长度为 4。

对应的前缀表为：

pi = [0, 0, 1, 2, 0, 1, 2, 3, 4]

KMP算法的步骤

构建部分匹配表：根据模式串生成前缀表 pi。
匹配过程：
- 使用两个指针 i 和 j，分别指向文本串和模式串的当前字符。
- 当 text[i] == pattern[j] 时，两个指针同时向后移动。
- 如果 j 达到模式串的长度，说明找到了匹配，记录匹配位置。
- 如果不匹配：
  - 如果 j > 0，则根据 pi[j - 1] 更新 j，即跳过已匹配的部分。
  - 如果 j == 0，则只移动 i。

KMP算法的Java实现

以下是 KMP算法的 Java 实现示例：

public class KMPAlgorithm {// 构建部分匹配表private int[] buildPrefixTable(String pattern) {int[] pi = new int[pattern.length()];int j = 0; // 前缀的长度for (int i = 1; i < pattern.length(); i++) {while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {j = pi[j - 1]; // 回退到上一个最长相等前后缀}if (pattern.charAt(i) == pattern.charAt(j)) {j++; // 找到匹配，增加前缀长度}pi[i] = j; // 更新前缀表}return pi;}// KMP匹配算法public void KMP(String text, String pattern) {int[] pi = buildPrefixTable(pattern); // 构建部分匹配表int j = 0; // 模式串的指针for (int i = 0; i < text.length(); i++) {while (j > 0 && text.charAt(i) != pattern.charAt(j)) {j = pi[j - 1]; // 回退到上一个最长相等前后缀}if (text.charAt(i) == pattern.charAt(j)) {j++; // 找到匹配}if (j == pattern.length()) {System.out.println("Pattern found at index: " + (i - j + 1));j = pi[j - 1]; // 继续寻找下一个匹配}}}public static void main(String[] args) {KMPAlgorithm kmp = new KMPAlgorithm();String text = "ABABDABACDABABCABAB";String pattern = "ABABCABAB";kmp.KMP(text, pattern); // 在文本中查找模式串}
}

代码解读

buildPrefixTable 方法：构建模式串的前缀表 pi，用于记录模式串中每个字符的最长相等前后缀的长度。
- j 表示当前前缀的长度，循环遍历模式串，更新前缀表。
- 在字符不匹配时，通过 pi 数组回退 j，找到合适的前缀长度。
KMP 方法：实现 KMP 字符串匹配算法。
- 使用两个指针 i 和 j，分别遍历文本串和模式串。
- 当字符匹配时，两个指针向后移动，若 j 达到模式串长度，说明找到了匹配。
- 输出匹配的位置，并根据 pi 数组更新 j，继续查找其他匹配。
main 方法：创建 KMPAlgorithm 实例，并在给定的文本串中查找指定的模式串。