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 数组）

目的：记录模式串中每个位置之前的最长可匹配前缀后缀的长度。

步骤：

1. 初始化一个与模式串长度相同的数组，初始值为 0。
2. 从模式串的第二个字符开始，依次计算每个位置的部分匹配值。

举例：模式串 "ABCDABD"

计算过程：

• 位置 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 数组，在匹配失败时，调整模式串的位置，而不回退文本串的指针。

步骤：

1. 初始化文本串指针 i=0，模式串指针 j=0。
2. 比较 Text[i] 与 Pattern[j]：
   • 如果匹配，i++，j++。
   • 如果不匹配：
     • 如果 j > 0，令 j = next[j - 1]，不移动 i，利用 next 数组跳过一部分字符。
     • 如果 j == 0，i++，从文本串的下一个字符继续匹配。
3. 当 j 达到模式串的长度，表示匹配成功。

8. 举个例子

文本串： "ABABDABACDABABCABAB"

模式串： "ABABCABAB"

next 数组：通过计算得到 [0, 0, 1, 2, 0, 1, 2, 3, 2]

匹配过程：

1. i=0，j=0，比较 'A' 与 'A'，匹配，i++，j++。
2. i=1，j=1，比较 'B' 与 'B'，匹配，i++，j++。
3. i=2，j=2，比较 'A' 与 'A'，匹配，i++，j++。
4. i=3，j=3，比较 'B' 与 'B'，匹配，i++，j++。
5. i=4，j=4，比较 'D' 与 'C'，不匹配。
   • j > 0，令 j = next[3] = 2，i 不变（回退模式串的位置）。
6. j=2，比较 'D' 与 'A'，不匹配。
   • j > 0，令 j = next[1] = 0，i 不变。
7. j=0，比较 'D' 与 'A'，不匹配。
   • j == 0，令 i++，i=5。
8. 重复上述步骤，直到 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 方法用于在文本串中查找模式串，返回匹配的起始位置。

三、总结

1. KMP 算法 通过借助模式串的部分匹配信息，避免重复比较，大大提高了匹配效率。
2. next 数组 是 KMP 算法的核心，它记录了模式串中每个位置之前的最长可匹配前缀后缀的长度。
3. 学习建议：
   • 多画图、多手算，理解 next 数组的构建过程。
   • 跟踪算法的匹配过程，加深理解。
   • 亲自实现一遍代码，调试运行，巩固所学。

四、常见问题解答

1. 为什么要使用 next 数组？
   • 因为当出现匹配失败时，next 数组告诉我们模式串中有多少字符是重复的，可以跳过这些重复的部分，减少比较次数。
2. KMP 算法的时间复杂度是多少？
   • KMP 算法的时间复杂度为 O(n)，其中 n 是文本串的长度。
3. 学习 KMP 算法的难点是什么？
   • 主要在于理解 next 数组的构建和应用，以及在匹配失败时如何利用 next 数组调整模式串的位置。