目录

KMP

基本介绍

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如下表所示 https://gitee.com/lienhui68/picStore/raw/master/null/20200704160625.png 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位置,如下图所示, https://gitee.com/lienhui68/picStore/raw/master/null/20200704161040.png

此时主字符串前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]位即可。如下图所示 https://gitee.com/lienhui68/picStore/raw/master/null/20200704162847.png

next数组

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

如何构建next数组? 求next数组的过程完全可以看成字符串匹配的过程,即以模式字符串为主字符串,以模式字符串的前缀为目标字符串,一旦字符串匹配成功,那么当前的next值就是匹配成功的字符串的长度。 具体来说,就是从模式字符串的第一位(注意,不包括第0位)开始对自身进行匹配运算。 在任一位置,能匹配的最长长度就是当前位置的next值。如下图所示(i是next数组的下标,j是模式字符串的下标) https://gitee.com/lienhui68/picStore/raw/master/null/WX20200704-184614@2x.png 下面关键的地方 当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; https://gitee.com/lienhui68/picStore/raw/master/null/20200704191844.png 我们看到,三幅图中,橙色块都是相等的, 如果存在次长公共序列,第二幅图表明,橙色块必然同时以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 算法?