KMP

2020-06-12 约 2250 字预计阅读 5 分钟次阅读

基本介绍

KMP算法由D.E.Knuth，J.H.Morris和V.R.Pratt同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法）

字符串的前缀和后缀

如果字符串A和B，存在A=BS，其中S是任意的非空字符串，那就称B为A的前缀。例如，”Harry”的前缀包括{”H”, ”Ha”, ”Har”, ”Harr”}，我们把所有前缀组成的集合，称为字符串的前缀集合。同样可以定义后缀A=SB，其中S是任意的非空字符串，那就称B为A的后缀，例如，”Potter”的后缀包括{”otter”, ”tter”, ”ter”, ”er”, ”r”}，然后把所有后缀组成的集合，称为字符串的后缀集合。要注意的是，字符串本身并不是自己的后缀。

部分匹配表

KMP算法的核心，是一个被称为部分匹配表(Partial Match Table)的数组。我觉得理解KMP的最大障碍就是很多人在看了很多关于KMP的文章之后，仍然搞不懂PMT中的值代表了什么意思。这里我们抛开所有的枝枝蔓蔓，先来解释一下这个数据到底是什么。

对于字符串“abababca”，它的PMT如下表所示 PMT中的值是字符串的前缀集合与后缀集合的交集中最长元素的长度。例如，对于”aba”，它的前缀集合为{”a”, ”ab”}，后缀集合为{”ba”, ”a”}。两个集合的交集为{”a”}，那么长度最长的元素就是字符串”a”了，长度为1，所以对于”aba”而言，它在PMT表中对应的值就是1。再比如，对于字符串”ababa”，它的前缀集合为{”a”, ”ab”, ”aba”, ”abab”}，它的后缀集合为{”baba”, ”aba”, ”ba”, ”a”}，两个集合的交集为{”a”, ”aba”}，其中最长的元素为”aba”，长度为3。

算法原理

在主字符串"ababababca"中查找模式字符串"abababca"，从起始位置开始匹配也是采用bf(brute force)，当主字符串匹配到i位置和模式字符串不匹配，此时模式字符串移动到j位置，如下图所示，

此时主字符串前j位和模式字符串的前j位相同，那么模式字符串指针j之前的后PMT[j-1]位与主字符串指针i之前的后PMT[j-1]位是相同的，又由于pmt的性质，模式字符串j指针之前的的后pmt[j-1]位与模式字符串的前pmt[j-1]位相同，所以主字符串中i指针之前的PMT[j−1]位就一定与模式字符串的第0位至第 PMT[j−1]位是相同的。这样一来，我们就可以将这些字符段的比较省略掉。具体的做法是，保持i指针不动，然后将j指针指向模式字符串的PMT[j −1]位即可。如下图所示

next数组

如果在j位失配，那么影响j指针回溯的位置的其实是第j−1位的PMT值，所以为了编程的方便，我们不直接使用PMT数组，而是将PMT数组整体向后偏移一位，第0位赋值-1(没有实际意义，纯粹为了编程方便)。我们把新得到的这个数组称为next数组。如下图所示

如何构建next数组？求next数组的过程完全可以看成字符串匹配的过程，即以模式字符串为主字符串，以模式字符串的前缀为目标字符串，一旦字符串匹配成功，那么当前的next值就是匹配成功的字符串的长度。具体来说，就是从模式字符串的第一位(注意，不包括第0位)开始对自身进行匹配运算。在任一位置，能匹配的最长长度就是当前位置的next值。如下图所示(i是next数组的下标，j是模式字符串的下标) 下面关键的地方 当i=7，j=4, p[i]=‘c’， p[j]=‘a’，此时next[7]等于多少？我们用图片来描述这个问题，橙色的A表示已经确定的最长公共序列，此时i坐标对应的值为绿色的T将要与开头的A后面的元素进行比较。如果比对失败，我们需要寻找次长公共序列B，然后T再与开头的B后面元素进行比对，依次类推直到T跟p[1]进行比较也不通过，那么next[i]=0; 我们看到，三幅图中，橙色块都是相等的，如果存在次长公共序列，第二幅图表明，橙色块必然同时以B开头且以B结尾。即，如第三幅图所示，这表明，T位置的次长公共序列长度，就是橙色块的最长公共序列长度。所以，next[7]的计算逻辑如下，i=7,j=4 p[i]和p[j]比较，相等则next[i]=j 否则p[7]和p[next[4]]比较，也就是p[7]和p[2]比较，不相等，再和p[next[2]]即p[0]比较，不相等，此时才可以断定next[7]=0 代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


public static int[] getNextArr(String pattern) {
        if (pattern.length() < 2) {
            throw new RuntimeException();
        }
        int[] next = new int[pattern.length()];
        next[0] = -1;
        char[] p = pattern.toCharArray();
        int i = 0;
        int j = -1;
        while (i < pattern.length()) {
            if (j == -1 || p[i] == p[j]) {
                i++;
                j++;
                if (i != pattern.length()) {
                    next[i] = j;
                }

            } else {
                j = next[j];
            }
        }
        return next;
    }

完整代码

 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
46
47
48
49
50
51
52
53
54
55
56
57
58


    /**
     * 字符串查找
     *
     * @param s1 主字符串
     * @param s2 模式字符串
     * @return 模式串出现过返回最早的位置，否则返回-1
     */
    public static int kmp(String s1, String s2) {
        int[] next = getNextArr(s2);
        //进行匹配
        for (int i = 0, j = 0; i < s1.length(); ) {
            if (s1.charAt(i) == s2.charAt(j)) {
                if (j == s2.length() - 1) {
                    return i - j;
                } else {
                    i++;
                    j++;
                }
            } else {
                if (next[j] == -1) {
                    i++; // 让下一个i所在字符和p[0]比较
                } else {
                    j = next[j];
                }
            }
        }
        return -1;

    }

    public static int[] getNextArr(String pattern) {
        if (pattern.length() < 2) {
            throw new RuntimeException();
        }
        int[] next = new int[pattern.length()];
        next[0] = -1;
        char[] p = pattern.toCharArray();
        int i = 0;
        int j = -1;
        while (i < pattern.length()) {
            if (j == -1 || p[i] == p[j]) {
                i++;
                j++;
                if (i != pattern.length()) {
                    next[i] = j;
                }

            } else {
                j = next[j];
            }
        }
        return next;
    }


    public static void main(String[] args) {
        System.out.println(kmp("abbaabbaaba", "abbaaba"));
    }

参考

如何更好地理解和掌握 KMP 算法?

目录

KMP