KMP算法：从理论到代码
KMP算法：从理论到代码 一、理论 1. 什么是KMP算法 KMP 算法，全称 Knuth-Morris-Pratt 算法，是由 Donald Knuth、James H. Morris 和 Vaughan Pratt 三位计算机科学家于 1977 年共同提出的一种高效的字符串匹配算法。它用于在一个文本串（Text）中查找一个模式串（Pattern）出现的位置，匹配过程中利用了已部分匹配的信息，避免了重复比较，从而大大提高了匹配效率。 2. 什么是字符串匹配 在开始之前，先了解一下 字符串匹配 的问题： 目的：在一段文本（Text）中查找一个特定的子串（Pattern）。 举例：在 "hello world" 中查找 "world"，目标是找到 "world" 在 "hello world" 中的位置。 3. 朴素的字符串匹配方法 最直接的想法是： 从文本的第一个字符开始，与模式串的第一个字符比较。 如果匹配，就继续比较下一个字符。 如果全部字符都匹配成功，说明找到了模式串。 如果中途有字符不匹配，就从文本的下一个字符开始，重复上述步骤。 问题在于：当文本很长，而模式串较短，且包含重复字符时，效率会很低，因为需要大量的重复比较。 4. KMP 算法的基本思想 KMP 算法的核心是 利用模式串本身的规律，避免重复比较。 当遇到不匹配时，不需要回到文本串的下一个字符，而是利用已经匹配的信息，跳过一些不必要的字符。 这通过 部分匹配表（next 数组） 实现。 5. 理解前缀和后缀 在构建部分匹配表之前，需要理解 前缀 和 后缀 的概念： 前缀：不包含最后一个字符的所有以第一个字符开始的连续子串。 后缀：不包含第一个字符的所有以最后一个字符结尾的连续子串。 举例：对于字符串 "ABCDAB"： 前缀包括："A"、"AB"、"ABC"、"ABCD"、"ABCDA" 后缀包括："BCDAB"、"CDAB"、"DAB"、"AB"、"B" 6. 构建部分匹配表（next 数组） 目的：记录模式串中每个位置之前的最长可匹配前缀后缀的长度。 步骤： 初始化一个与模式串长度相同的数组，初始值为 0。 从模式串的第二个字符开始，依次计算每个位置的部分匹配值。 举例：模式串 "ABCDABD" 位置索引（从 0 开始） 字符 部分匹配值（next 值） 0 A 0 1 B 0 2 C 0 3 D 0 4 A 1 5 B 2 6 D 0 计算过程： 位置 0：只有一个字符 'A'，部分匹配值为 0。 位置 1：前缀 'A'，后缀 'B'，不匹配，部分匹配值为 0。 位置 2：前缀有 'A'、'AB'，后缀有 'BC'、'C'，不匹配，部分匹配值为 0。 位置 3：同理，部分匹配值为 0。 位置 4： 前缀有：'A'、'AB'、'ABC'、'ABCD' 后缀有：'BCDA'、'CDA'、'DA'、'A' 前缀 'A' 与后缀 'A' 匹配，部分匹配值为 1。 位置 5： 前缀有：'A'、'AB'、'ABC'、'ABCD'、'ABCDA' 后缀有：'BCDAB'、'CDAB'、'DAB'、'AB'、'B' 前缀 'AB' 与后缀 'AB' 匹配，部分匹配值为 2。 位置 6：没有匹配，部分匹配值为 0。 7. KMP 算法匹配过程 利用 next 数组，在匹配失败时，调整模式串的位置，而不回退文本串的指针。 步骤： 初始化文本串指针 i=0，模式串指针 j=0。 比较 Text[i] 与 Pattern[j]： 如果匹配，i++，j++。 如果不匹配： 如果 j > 0，令 j = next[j - 1]，不移动 i，利用 next 数组跳过一部分字符。 如果 j == 0，i++，从文本串的下一个字符继续匹配。 当 j 达到模式串的长度，表示匹配成功。 8. 举个例子 文本串： "ABABDABACDABABCABAB" 模式串： "ABABCABAB" next 数组：通过计算得到 [0, 0, 1, 2, 0, 1, 2, 3, 2] 匹配过程： i=0，j=0，比较 'A' 与 'A'，匹配，i++，j++。 i=1，j=1，比较 'B' 与 'B'，匹配，i++，j++。 i=2，j=2，比较 'A' 与 'A'，匹配，i++，j++。 i=3，j=3，比较 'B' 与 'B'，匹配，i++，j++。 i=4，j=4，比较 'D' 与 'C'，不匹配。 j > 0，令 j = next[3] = 2，i 不变（回退模式串的位置）。 j=2，比较 'D' 与 'A'，不匹配。 j > 0，令 j = next[1] = 0，i 不变。 j=0，比较 'D' 与 'A'，不匹配。 j == 0，令 i++，i=5。 重复上述步骤，直到 j 达到模式串的长度，匹配成功，或 i 超过文本串长度，匹配失败。 二、代码 KMP算法的Java实现 public class KMPAlgorithm { // 构建 next 数组 public static int[] buildNext(String pattern) { int m = pattern.length(); int[] next = new int[m]; int j = 0; // 已匹配的前缀长度 for (int i = 1; i < m; i++) { // 当出现不匹配，且 j > 0 时，回退到前一个可能匹配的位置 while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) { j = next[j - 1]; } // 如果字符匹配，已匹配的前缀长度加 1 if (pattern.charAt(i) == pattern.charAt(j)) { j++; } next[i] = j; } return next; } // KMP 搜索算法 public static int kmpSearch(String text, String pattern) { int n = text.length(); int m = pattern.length(); int[] next = buildNext(pattern); int j = 0; // 模式串指针 for (int i = 0; i < n; i++) { // 出现不匹配，且 j > 0 时，按照 next 数组回退 while (j > 0 && text.charAt(i) != pattern.charAt(j)) { j = next[j - 1]; } // 如果字符匹配，模式串指针加 1 if (text.charAt(i) == pattern.charAt(j)) { j++; } // 如果匹配成功，返回匹配的起始位置 if (j == m) { return i - m + 1; } } // 未找到匹配 return -1; } public static void main(String[] args) { String text = "ABABDABACDABABCABAB"; String pattern = "ABABCABAB"; int result = kmpSearch(text, pattern); if (result == -1) { System.out.println("未找到匹配的模式串。"); } else { System.out.println("模式串出现在位置：" + result); } } } 解释： buildNext 方法用于构建 next 数组。 kmpSearch 方法用于在文本串中查找模式串，返回匹配的起始位置。 三、总结 KMP 算法 通过借助模式串的部分匹配信息，避免重复比较，大大提高了匹配效率。 next 数组 是 KMP 算法的核心，它记录了模式串中每个位置之前的最长可匹配前缀后缀的长度。 学习建议： 多画图、多手算，理解 next 数组的构建过程。 跟踪算法的匹配过程，加深理解。 亲自实现一遍代码，调试运行，巩固所学。 四、常见问题解答 为什么要使用 next 数组？ 因为当出现匹配失败时，next 数组告诉我们模式串中有多少字符是重复的，可以跳过这些重复的部分，减少比较次数。 KMP 算法的时间复杂度是多少？ KMP 算法的时间复杂度为 O(n)，其中 n 是文本串的长度。 学习 KMP 算法的难点是什么？ 主要在于理解 next 数组的构建和应用，以及在匹配失败时如何利用 next 数组调整模式串的位置。
