KMP算法

发表于 更新于 分类于 ， 阅读次数： 本文字数： 925 阅读时长 ≈ 3 分钟

在计算机科学中，Knuth-Morris-Pratt 字符串查找算法（简称 KMP 算法）可在一个主文本字符串 S 内查找一个词 W 的出现位置。此算法通过运用对这个词在不匹配时本身就包含足够的信息来确定下一个匹配将在哪里开始的发现，从而避免重新检查先前匹配的字符。

该算法由唐纳德·克努斯（Donald Knuth）和沃恩·普拉特（Vaughan Pratt）于 1970 年提出，由詹姆斯·h·莫里斯（James H. Morris）独立完成，最终由三人于 1977 年联合发表。这是第一个字符串匹配的线性时间算法。

KMP算法

KMP算法的来源

Knuth-Morris-Pratt 字符串查找算法，简称为 “KMP算法”，常用于在一个文本串 S 内查找一个模式串 P 的出现位置，这个算法由 Donald Knuth、Vaughan Pratt、James H. Morris 三人于 1977 年联合发表，故取这 3 人的姓氏命名此算法。

前缀和后缀的定义

  • “前缀”指除最后一个字符外，一个字符串的全部头部组合；
  • “后缀”指除第一个字符外，一个字符串的全部尾部组合。

例如：

字符串 “blue”
前缀 “b” “bl” “blu”
后缀 “lue” “ue” “e”

KMP 算法的关键

KMP 利用之前已经部分匹配这个有效信息，保持 i 不回溯，通过修改 j 的位置，让模式串尽量地移动到有效的位置，而模式串移动的信息存在 next 数组中。

KMP 算法的关键是 next 数组的计算，next 数组的计算只与模式串有关，next 中存储的值为当前下标之前的子串的 最长相同前缀和后缀的长度。如模式串 "ABCDABD" 的 next 数组：

i 0 1 2 3 4 5 6
模式串 A B C D A B D
next[i] -1 0 0 0 0 1 2

注：next[0] 设为 -1

BF 算法（ Brute-Force 暴力匹配）

假设现在我们面临这样一个问题：有一个文本串 S，和一个模式串 P，现在要查找 P 在 S 中的位置，怎么查找呢？

如果用暴力匹配的思路，并假设现在文本串 S 匹配到 i 位置，模式串 P 匹配到 j 位置，则有：

  • 如果当前字符匹配成功（即 S[i] == P[j] ），则 i++， j++，继续匹配下一个字符；

  • 如果失配（即 S[i] != P[j] ），令 i = i - j + 1， j = 0。相当于每次匹配失败时， i 回溯， j 被置为 0。

用 Java 实现的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class BruteForceMatch {
    public static int search(char[] s, char[] p){
        int i = 0, j = 0;
        while (i < s.length && j < p.length){
            if (s[i] == p[j]){
                i++;
                j++;
            }else {
                i = i - j + 1;
                j = 0;
            }
        }
        return (j == p.length) ? i - j : -1;
    }

    public static void main(String[] args){
        char[] s = "BBC ABCDAB ABCDABCDABDE".toCharArray();
        char[] p = "ABCDABD".toCharArray();
        System.out.println(search(s, p));
    }
}

next数组计算

  • next[0] = -1
  • 如果已知 next[j] = k，如何求出 next[j+1]
    • 如果 p[j] == p[k] , 则 next[j+1] = next[j] + 1 = k + 1;
    • 如果 p[j] != p[k], 则令 k = next[k], 如果此时 p[j] == p[k],则 next[j+1] = k+1, 如果不相等, 则继续递归前缀索引,令 k = next[k], 继续判断, 直至 k = -1 (即 k = next[0] )或者 p[j] == p[k] 为止
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static int[] getNextArray(char[] p){
    int[] next = new int[p.length];
    int k = -1, j = 0;
    next[0] = -1;
    while (j < p.length - 1){
        if (k == -1 || p[k] == p[j]){
            k++;
            j++;
            next[j] = k;
        }else {
            k = next[k];
        }
    }
    return next;
}

KMP算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
public class KMP {
    public static int[] getNextArray(char[] p){
        int[] next = new int[p.length];
        int k = -1, j = 0;
        next[0] = -1;
        while (j < p.length - 1){
            if (k == -1 || p[k] == p[j]){
                k++;
                j++;
                next[j] = k;
            }else {
                k = next[k];
            }
        }
        return next;
    }

    public static int[] getNextArray(String p){
        return KMP.getNextArray(p.toCharArray());
    }

    public static int search(char[] s, char[] p){
        int[] next = KMP.getNextArray(p);
        int i = 0, j = 0;
        while (i < s.length && j < p.length){
            if (j == -1 || s[i] == p[j]){
                i++;
                j++;
            }else {
                j = next[j];
            }
        }
        return (j == p.length) ? i - j : -1;
    }

    public static int search(String s, String p){
        return KMP.search(s.toCharArray(), p.toCharArray());
    }

    public static void main(String[] args) {
        String s = "BBC ABCDAB ABCDABCDABDE";
        String p = "ABCDABD";
        System.out.println(KMP.search(s, p));
    }
}

时间复杂度

BF： \(O(n*m)\)，BF 在失配时，主串需要回溯，然后从下一个字符开始重新与模式串进行匹配。

KMP： \(O(n+m)\)，求 next 数组的时间复杂度是 \(O(m)\)， KMP 失配时，主串不需要回溯，时间复杂度为 \(O(n)\)，整体时间复杂度为 \(O(n+m)\)

最好情况：每趟匹配不成功都是在第一个字符，即每趟都只需匹配一次就知道该趟是否匹配，O(n+m)

最坏情况：每趟匹配不成功都是在最后一个字符，O(n*m)

References

https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm

https://www.jianshu.com/p/e2bd1ee482c3

https://blog.csdn.net/v_july_v/article/details/7041827