KMP 算法教程：手把手教你实现模式匹配 – wiki基地

作者： /

KMP 算法教程：手把手教你实现模式匹配

前言：为什么我们需要 KMP？

在计算机科学中，字符串匹配是一个基础且重要的任务。想象一下你正在使用一个文本编辑器，想要搜索某个特定的词语；或者在一个基因序列中寻找一段特定的 DNA 片段；再或者在网络流量中检测特定的恶意模式。这些都属于字符串匹配的范畴。

最直观的字符串匹配算法是“朴素匹配算法”（Naive String Matching Algorithm）。它的思想很简单：将模式串（Pattern）P 的第一个字符与文本串（Text）T 的第一个字符对齐，然后逐个比较。如果全部匹配，则找到一个匹配；如果出现不匹配，就将模式串 P 向右移动一个位置，再次从头开始比较。

朴素匹配算法的缺点：

考虑以下例子：
文本串 T = “ABABAABABA”
模式串 P = “ABABA”

  1. 第一次尝试：
    T: A B A B A A B A B A
    P: A B A B A
    匹配成功！

  2. 第二次尝试（假设我们想找所有匹配）：
    T: A B A B A A B A B A
    P: A B A B A
    在 P[0] 和 T[1] 处匹配 ‘B’，但在 P[1] 和 T[2] 处不匹配 ‘A’ 和 ‘B’。模式串需要继续右移。

问题在于，当朴素匹配算法发现一个不匹配时，它会简单地将模式串向右移动一位，然后丢弃之前已经匹配成功的信息。例如，在 T = “AAAAAB” 和 P = “AAAB” 的例子中：

T: A A A A A B
P: A A A B
^ ^ ^
前三个 ‘A’ 匹配成功，在第四个字符 ‘A’ 和 ‘B’ 处不匹配。

朴素算法会将 P 移动一位：
T: A A A A A B
P: A A A B
^ ^
又得从头开始比较。

很明显，朴素匹配算法在最坏情况下（例如 T = “AAAAAAB”, P = “AAAB” 这种模式串重复字符很多的情况）的性能非常糟糕，时间复杂度为 O(N * M)，其中 N 是文本串长度，M 是模式串长度。这在处理大型文本时是不可接受的。

KMP 算法（Knuth-Morris-Pratt Algorithm） 应运而生，它以三位发明者 Donald Knuth、James H. Morris 和 Vaughan Pratt 的名字命名。KMP 算法通过巧妙地利用模式串自身的特性，避免了在文本串中的不必要回溯，从而将时间复杂度优化到线性的 O(N + M)。

那么，KMP 究竟是如何实现这一点的呢？让我们一步步揭开 KMP 的神秘面纱。

KMP 算法的核心思想：不浪费已知信息

KMP 算法的关键在于，当模式串 P 在文本串 T 的某个位置发生不匹配时，它不会像朴素算法那样简单地将模式串 P 右移一位并重新开始比较。相反，KMP 会根据模式串 P 自身的特性，计算出模式串 P 应该向右“跳跃”多少位，才能使下一次比较尽可能地有效，并且避免重复比较已经匹配过的字符。

这个“自身特性”就是模式串的“最长公共前后缀”。

1. 前缀与后缀

  • 前缀（Prefix）：一个字符串从开头开始的任意子串（不包括字符串本身）。
    例如，字符串 “ABCABA” 的前缀有：”A”, “AB”, “ABA”, “ABAB”, “ABABC”。
  • 后缀（Suffix）：一个字符串从结尾开始的任意子串（不包括字符串本身）。
    例如，字符串 “ABCABA” 的后缀有：”A”, “BA”, “ABA”, “CABA”, “BCABA”。
  • 真前缀（Proper Prefix）：不包括字符串本身的前缀。
  • 真后缀（Proper Suffix）：不包括字符串本身的后缀。

2. 最长公共前后缀 (LPS – Longest Proper Prefix which is also a Suffix)

对于模式串 P 的任意一个前缀 P[0…j-1]，我们希望找到它的一个真前缀，同时也是它的一个真后缀，并且这个真前缀/真后缀的长度是所有符合条件的中最长的。

听起来有点绕？我们举个例子：

模式串 P = “ABABCABAB”

  • P[0…0] = “A”

    • 真前缀：无
    • 真后缀：无
    • 最长公共前后缀长度：0

  • P[0…1] = “AB”

    • 真前缀：”A”
    • 真后缀：”B”
    • 最长公共前后缀长度：0

  • P[0…2] = “ABA”

    • 真前缀：”A”, “AB”
    • 真后缀：”A”, “BA”
    • 公共前后缀：”A”
    • 最长公共前后缀长度：1 (“A”)

  • P[0…3] = “ABAB”

    • 真前缀：”A”, “AB”, “ABA”
    • 真后缀：”B”, “AB”, “BAB”
    • 公共前后缀：”AB”
    • 最长公共前后缀长度：2 (“AB”)

  • P[0…4] = “ABABC”

    • 真前缀：”A”, “AB”, “ABA”, “ABAB”
    • 真后缀：”C”, “BC”, “ABC”, “BABC”
    • 公共前后缀：无
    • 最长公共前后缀长度：0

  • P[0…5] = “ABABCA”

    • 真前缀：”A”, “AB”, “ABA”, “ABAB”, “ABABC”
    • 真后缀：”A”, “CA”, “BCA”, “ABCA”, “BABCA”
    • 公共前后缀：”A”
    • 最长公共前后缀长度：1 (“A”)

  • P[0…6] = “ABABCAB”

    • 真前缀：”A”, “AB”, “ABA”, “ABAB”, “ABABC”, “ABABCA”
    • 真后缀：”B”, “AB”, “CAB”, “BCAB”, “ABCAB”, “BABCA”
    • 公共前后缀：”AB”
    • 最长公共前后缀长度：2 (“AB”)

  • P[0…7] = “ABABCABA”

    • 真前缀：”A”, “AB”, “ABA”, “ABAB”, “ABABC”, “ABABCA”, “ABABCAB”
    • 真后缀：”A”, “BA”, “ABA”, “CABA”, “BCABA”, “ABCABA”, “BABCABA”
    • 公共前后缀：”A”, “ABA”
    • 最长公共前后缀长度：3 (“ABA”)

  • P[0…8] = “ABABCABAB”

    • 真前缀：”A”, “AB”, “ABA”, “ABAB”, “ABABC”, “ABABCA”, “ABABCAB”, “ABABCABA”
    • 真后缀：”B”, “AB”, “BAB”, “ABAB”, “CABAB”, “BCABAB”, “ABCABAB”, “BABCABAB”
    • 公共前后缀：”AB”, “ABAB”
    • 最长公共前后缀长度：4 (“ABAB”)

我们将这些长度存储在一个数组中，通常称为 lps 数组（或 next 数组），它记录了模式串 P 中每个前缀的最长公共前后缀的长度。

对于 P = “ABABCABAB”，其 lps 数组为：
索引：0 1 2 3 4 5 6 7 8
字符：A B A B C A B A B
lps：0 0 1 2 0 1 2 3 4

3. lps 数组的作用：指导模式串的移动

假设我们在比较文本串 T 和模式串 P 时，在 T[i] 和 P[j] 处发现不匹配：T[i] != P[j]。
这意味着 P[0...j-1] 已经成功地匹配了 T[i-j...i-1]。

朴素算法 会简单地将 P 向右移动一个字符，然后从 P[0] 再次比较。
KMP 算法 则会利用 lps[j-1] 的值。

lps[j-1] 告诉我们，在已匹配的前缀 P[0...j-1] 中，最长的真前缀同时也是真后缀的长度是 lps[j-1]。
这意味着 P[0...lps[j-1]-1]（一个前缀）与 P[j-lps[j-1]...j-1]（一个后缀）是相同的。
由于 P[0...j-1] 已经与 T[i-j...i-1] 匹配，所以 P[j-lps[j-1]...j-1] 也与 T[i-lps[j-1]...i-1] 匹配。

因此，当 P[j] 与 T[i] 不匹配时，我们可以将模式串 P 移动到新的位置，使得 P[lps[j-1]] 对齐到 T[i]。换句话说，我们把模式串的 j 指针回溯到 lps[j-1] 的位置，然后继续比较 T[i] 和 P[lps[j-1]]。这样就避免了文本串 T 指针的回溯。

如果 j 已经为 0（即 P[0] 就和 T[i] 不匹配），那么我们只能将 T 指针 i 向右移动一位，模式串 P 指针 j 仍然保持在 0。

算法实现步骤

KMP 算法主要分为两个阶段：

  1. 预处理阶段： 计算模式串 P 的 lps 数组。
  2. 匹配阶段： 使用 lps 数组在文本串 T 中查找模式串 P。

阶段一：构建 lps 数组 (Knuth-Morris-Pratt’s preprocessing)

目标： 对于给定的模式串 P，构建一个同等长度的 lps 数组，其中 lps[k] 存储 P[0...k] 的最长公共前后缀的长度。

算法思路：
使用两个指针：
* length：表示当前已知的最长公共前后缀的长度。它也代表模式串 P 中正在比较的前缀的下一个字符的索引。
* i：遍历模式串 P 的当前字符的索引（从 1 开始）。

步骤：
1. 初始化 lps[0] = 0。
2. length = 0 (lps 的长度)。
3. i = 1 (从 P 的第二个字符开始处理)。
4. 当 i < M (模式串长度) 时，循环执行以下操作：
* 如果 P[i] == P[length]：
这表示我们找到了一个更长的公共前后缀。
length 自增 1。
lps[i] 赋值为 length。
i 自增 1。
* 如果 P[i] != P[length]：
这表示当前字符不匹配。
* 如果 length != 0：
我们不能直接将 length 置为 0。因为当前 length 之前的 P[0...length-1] 已经匹配了 P[i-length...i-1]，我们应该尝试寻找 P[0...length-1] 的次长公共前后缀。这个信息就存储在 lps[length-1] 中。
所以，将 length 更新为 lps[length-1]。i 不变，继续尝试用新的 length 对应的字符与 P[i] 匹配。
* 如果 length == 0：
这表示 P[i] 和 P[0] 都不匹配，且没有更短的公共前后缀可以利用。
lps[i] 赋值为 0。
i 自增 1。

举例：构建 lps 数组 for P = “ABABCABAB”

i P[i] length P[length] 比较 P[i] 与 P[length] 动作 lps 数组（当前状态）
0 (初始化) lps[0]=0 [0]
1 B 0 A B != A length 为 0，lps[1]=0, i++ [0, 0]
2 A 0 A A == A length++ (1), lps[2]=1, i++ [0, 0, 1]
3 B 1 B B == B length++ (2), lps[3]=2, i++ [0, 0, 1, 2]
4 C 2 A C != A length 不为 0，length = lps[length-1] (lps[1]=0) [0, 0, 1, 2]
C 0 A C != A length 为 0，lps[4]=0, i++ [0, 0, 1, 2, 0]
5 A 0 A A == A length++ (1), lps[5]=1, i++ [0, 0, 1, 2, 0, 1]
6 B 1 B B == B length++ (2), lps[6]=2, i++ [0, 0, 1, 2, 0, 1, 2]
7 A 2 A A == A length++ (3), lps[7]=3, i++ [0, 0, 1, 2, 0, 1, 2, 3]
8 B 3 B B == B length++ (4), lps[8]=4, i++ [0, 0, 1, 2, 0, 1, 2, 3, 4]

循环结束，lps 数组构建完成：[0, 0, 1, 2, 0, 1, 2, 3, 4]。

阶段二：KMP 匹配算法

目标： 在文本串 T 中查找模式串 P 的所有匹配。

算法思路：
使用两个指针：
* i：文本串 T 的当前字符索引。
* j：模式串 P 的当前字符索引。

步骤：
1. 初始化 i = 0, j = 0。
2. 当 i < N (文本串长度) 时，循环执行以下操作：
* 如果 P[j] == T[i]：
匹配成功一个字符。
i 自增 1。
j 自增 1。
* 如果 j == M (模式串长度)：
恭喜！找到一个匹配。匹配开始于 T[i-j] 处。
记录匹配位置。
然后，为了查找下一个可能的匹配，我们利用 lps 数组：将 j 更新为 lps[j-1]。这意味着我们利用了模式串的重叠性质，将模式串向前“滑动”到下一个可能匹配的位置。
* 如果 P[j] != T[i]：
不匹配发生。
* 如果 j != 0：
我们不能简单地将 j 置为 0。P[0...j-1] 已经和 T[i-j...i-1] 匹配成功。根据 lps 数组的定义，P[0...lps[j-1]-1] 是 P[0...j-1] 的最长公共前后缀。因此，我们可以将模式串 P 的 j 指针回溯到 lps[j-1] 处，继续尝试匹配 T[i] 和 P[lps[j-1]]。
j 更新为 lps[j-1]。
* 如果 j == 0：
这表示 P[0] 就和 T[i] 不匹配。没有前缀可以利用。
i 自增 1（文本串指针前进）。j 仍然保持在 0。

举例：KMP 匹配 for T = “ABABDABACDABABCABAB”, P = “ABABCABAB”
lps 数组 for P = “ABABCABAB” 是 [0, 0, 1, 2, 0, 1, 2, 3, 4]。

i (T) j (P) T[i] P[j] 比较 T[i] 与 P[j] 动作
0 0 A A T[0]==P[0] i++, j++
1 1 B B T[1]==P[1] i++, j++
2 2 A A T[2]==P[2] i++, j++
3 3 B B T[3]==P[3] i++, j++
4 4 D C T[4]!=P[4] j!=0 (j=4)，j = lps[j-1] (lps[3]=2) -> j=2
4 2 D A T[4]!=P[2] j!=0 (j=2)，j = lps[j-1] (lps[1]=0) -> j=0
4 0 D A T[4]!=P[0] j==0，i++ -> i=5
5 0 A A T[5]==P[0] i++, j++
6 1 B B T[6]==P[1] i++, j++
7 2 A A T[7]==P[2] i++, j++
8 3 C B T[8]!=P[3] j!=0 (j=3)，j = lps[j-1] (lps[2]=1) -> j=1
8 1 C B T[8]!=P[1] j!=0 (j=1)，j = lps[j-1] (lps[0]=0) -> j=0
8 0 C A T[8]!=P[0] j==0，i++ -> i=9
9 0 D A T[9]!=P[0] j==0，i++ -> i=10
10 0 A A T[10]==P[0] i++, j++
11 1 B B T[11]==P[1] i++, j++
12 2 A A T[12]==P[2] i++, j++
13 3 B B T[13]==P[3] i++, j++
14 4 C C T[14]==P[4] i++, j++
15 5 A A T[15]==P[5] i++, j++
16 6 B B T[16]==P[6] i++, j++
17 7 A A T[17]==P[7] i++, j++
18 8 B B T[18]==P[8] i++, j++
19 9 j == M (M=9) 匹配成功！ 模式串在 T[i-j] = T[19-9] = T[10] 处找到。
j = lps[j-1] (lps[8]=4) -> j=4
19 4 (i 已到 T 结尾) 循环结束

在这个例子中，模式串 “ABABCABAB” 在文本串 T 的索引 10 处被发现。

代码实现 (Java 示例)

“`java
public class KMPAlgorithm {

/**
 * 计算模式串的LPS（Longest Proper Prefix which is also a Suffix）数组。
 * LPS数组用于在不匹配时，确定模式串需要“滑动”多少位。
 *
 * @param pattern 模式串
 * @return LPS数组
 */
public int[] computeLPSArray(String pattern) {
    int m = pattern.length();
    int[] lps = new int[m]; // lps[i] 存储 pattern[0...i] 的最长公共前后缀长度

    int length = 0; // length 是当前已经计算出的最长公共前后缀的长度
    int i = 1;      // i 是当前正在计算的字符的索引，从模式串的第二个字符开始

    lps[0] = 0; // 第一个字符的前缀（自身）没有真前缀和真后缀，所以长度为0

    // 循环计算 lps[i] for i = 1 to m-1
    while (i < m) {
        if (pattern.charAt(i) == pattern.charAt(length)) {
            // 如果当前字符与 pattern[length] 匹配，
            // 说明找到了一个更长的公共前后缀
            length++;
            lps[i] = length;
            i++;
        } else {
            // 如果不匹配
            if (length != 0) {
                // 如果 length 不为 0，说明之前有匹配的前缀
                // 我们不能简单地将 length 设为 0
                // 而是根据 lps[length-1] 的值，回溯 length
                // 比如 pattern = "ABAB", i = 3, pattern[i] = 'B'
                // pattern[length] = pattern[2] = 'A'
                // length = lps[length-1] (lps[1]=0)
                length = lps[length - 1];
                // 注意：这里 i 不变，因为我们只是回溯 length，
                // 还需要用新的 pattern[length] 和 pattern[i] 再次比较
            } else {
                // 如果 length 已经为 0，且当前字符仍不匹配 pattern[0]
                // 说明没有公共前后缀可以利用
                lps[i] = 0;
                i++;
            }
        }
    }
    return lps;
}

/**
 * 使用KMP算法在文本串中查找模式串的所有匹配。
 *
 * @param text    文本串
 * @param pattern 模式串
 */
public void KMPSearch(String text, String pattern) {
    int n = text.length();    // 文本串长度
    int m = pattern.length(); // 模式串长度

    // 1. 预处理阶段：计算LPS数组
    int[] lps = computeLPSArray(pattern);

    int i = 0; // 指向文本串的当前字符索引
    int j = 0; // 指向模式串的当前字符索引

    while (i < n) {
        // 2. 匹配阶段：
        if (pattern.charAt(j) == text.charAt(i)) {
            // 如果当前字符匹配，则两个指针都向前移动
            i++;
            j++;
        }

        if (j == m) {
            // 如果 j 达到了模式串的长度，说明找到一个完整匹配
            System.out.println("在索引 " + (i - j) + " 处找到模式串。");

            // 为了查找下一个可能的匹配，利用LPS数组进行模式串的“滑动”
            // 将 j 回溯到 lps[j-1]，表示模式串的下一个匹配将从这个位置开始
            j = lps[j - 1];
        } else if (i < n && pattern.charAt(j) != text.charAt(i)) {
            // 如果当前字符不匹配
            if (j != 0) {
                // 如果 j 不为 0，说明模式串前面已经有部分匹配
                // 根据LPS数组回溯 j 指针，避免文本串 i 指针的回溯
                j = lps[j - 1];
            } else {
                // 如果 j 已经为 0，且仍然不匹配 pattern[0]
                // 说明没有前缀可以利用，只能让文本串 i 指针向前移动一位
                i++;
            }
        }
    }
}

public static void main(String[] args) {
    KMPAlgorithm kmp = new KMPAlgorithm();

    String text1 = "ABABDABACDABABCABAB";
    String pattern1 = "ABABCABAB";
    System.out.println("文本: " + text1);
    System.out.println("模式: " + pattern1);
    kmp.KMPSearch(text1, pattern1); // 预期输出: 在索引 10 处找到模式串。
    System.out.println("--------------------");

    String text2 = "AAAAABAAAB";
    String pattern2 = "AAAB";
    System.out.println("文本: " + text2);
    System.out.println("模式: " + pattern2);
    kmp.KMPSearch(text2, pattern2); // 预期输出: 在索引 2 处找到模式串。在索引 6 处找到模式串。
    System.out.println("--------------------");

    String text3 = "ABCDEFG";
    String pattern3 = "XYZ";
    System.out.println("文本: " + text3);
    System.out.println("模式: " + pattern3);
    kmp.KMPSearch(text3, pattern3); // 预期输出: 无匹配
    System.out.println("--------------------");

    String text4 = "AAAAAAA";
    String pattern4 = "AAA";
    System.out.println("文本: " + text4);
    System.out.println("模式: " + pattern4);
    kmp.KMPSearch(text4, pattern4); // 预期输出: 0, 1, 2, 3, 4
    System.out.println("--------------------");
}

}
“`

复杂度分析

时间复杂度

  1. computeLPSArray 函数（预处理阶段）:

    • 在 while 循环中，i 从 1 遍历到 m-1。
    • 在每次循环中，i 至少会 i++ 一次（在 if 块中或 else if (length == 0) 块中）。
    • length 在 if 块中 ++，在 else if (length != 0) 块中 length = lps[length-1] (即 length 变小)。
    • length 的最大值是 m-1，最小值是 0。length 每次减少，最多减少到 0。
    • 实际上，i 每次都会递增，因此 i 总共进行 M 次迭代。
    • 因此，computeLPSArray 的时间复杂度是 O(M)，其中 M 是模式串的长度。

  2. KMPSearch 函数（匹配阶段）:

    • 在 while 循环中，i 从 0 遍历到 n-1。
    • 在每次循环中，i 至少会 i++ 一次（在 if 块中或 else if (j == 0) 块中）。
    • j 在 if 块中 ++，在 else if (j != 0) 块中 j = lps[j-1] (即 j 变小)。
    • j 的最大值是 m-1，最小值是 0。j 每次减少，最多减少到 0。
    • 与 computeLPSArray 类似，文本串指针 i 永远不会回溯，它只会单向前进。在最坏情况下，i 会遍历整个文本串一次。
    • 因此，KMPSearch 的时间复杂度是 O(N)，其中 N 是文本串的长度。

总时间复杂度：O(M + N)。这是 KMP 算法相较于朴素算法（O(N * M)）的巨大优势，实现了线性时间复杂度的匹配。

空间复杂度

KMP 算法需要额外存储一个 lps 数组，其大小与模式串的长度 M 相同。
因此，空间复杂度是 O(M)。

KMP 算法的优点与应用

优点：
1. 高效性： 实现了线性的时间复杂度 O(N + M)，在大规模文本匹配中表现卓越。
2. 无回溯： 文本串指针 i 永远不会回溯，这对于流式数据处理（如网络数据包分析）非常有益。
3. 确定性： 算法流程清晰，没有随机性，易于理解和实现（一旦理解了 lps 数组）。

应用场景：
1. 文本编辑器和搜索工具： 实现高效的“查找”和“替换”功能。
2. 生物信息学： 在 DNA 或蛋白质序列中查找特定的基因片段或蛋白质结构模式。
3. 网络入侵检测系统 (NIDS)： 识别网络流量中是否存在已知的攻击签名或恶意模式。
4. 编译器和解释器： 词法分析阶段识别关键字和标识符。
5. 数据压缩： Lempel-Ziv 族压缩算法中会用到字符串匹配。
6. 文件比较工具 (diff)： 在比较文件差异时，可以利用字符串匹配来找出相同或不同的部分。

总结与展望

KMP 算法是一个经典的字符串匹配算法，它的精髓在于“未雨绸缪”——通过预先分析模式串自身的结构（即 lps 数组），在匹配失败时能够智能地调整模式串的位置，避免了不必要的回溯。这使得 KMP 算法在理论和实践中都具有重要的地位。

虽然理解 lps 数组的构建和运用可能需要一些时间和练习，但一旦掌握，你将拥有一个强大的工具来解决各种字符串匹配问题。希望这篇教程能够帮助你手把手地理解并实现 KMP 算法。多加练习，例如尝试用不同的模式串和文本串进行匹配，或者尝试自己画出 lps 数组的构建过程和匹配过程，你将对 KMP 有更深刻的理解。

模式匹配的世界远不止 KMP，还有 Rabin-Karp、Boyer-Moore 等其他高效算法，它们各有特点和适用场景。但 KMP 作为其中一个优雅且基础的算法，是学习高级字符串处理技术的绝佳起点。

发表评论

您的邮箱地址不会被公开。 必填项已用 * 标注

滚动至顶部