菜鸟算法图解基础------ 万字详解KMP_菜鸟教程图示算法

字符串匹配

让我们来看一个例子：字符串A和B，如何判断B是否是A的子串，如果是，返回B在A中第一次出现的位置？

我们定义 ：

• 字符串A为主串
• 字符串B为模式串
  我们接下来用模式串来匹配主串

1.1 BF解法（暴力）

第一轮 ： 我们分别从主串的首位和模式串的首位开始， 把主串和模式串的字符逐个比较：

这里我们明显发现，主串首位字符是a, 模式串首位字符是b，俩个字符并不匹配
第二轮：将模式串整体向后移一位， 从主串的第二位开始和模式串进行字符比较

主串的第二位是b， 模式串的第二位是c, 俩者并不匹配
第三轮：将模式串整体向后移一位， 从主串的第三位开始和模式串进行字符比较

主串的第三位和模式串的第一位匹配，我们继续进行比较

主串的第四位和模式串的第二位匹配，我们继续进行比较

俩者匹配完成，可以得到结果，模式串c d e是主串a b c d e f 的子串，在主串中第一次出现位置下标是2

假设主串A的长度是m， 模式串B的长度是n，
A: aaaaaaaaaab
B: aaab
轻松得知我们需要比较n * m次才能的到最终结果
那么BF算法的最坏时间复杂度是O(mn)。

那么我们该如何进行改进呢?

1.2 RK算法

RK算法的全称是Rabin-Karp，是由算法的两位发明者Rabin和Karp的名字来命名的。听起来很牛啊，RK算
法通过比较两个字符串的哈希值来进行优化

简单来说： 每个字符串都可以通过hash算法转换到一个整数，这个数就是hashcode

• 按位相加

这是最简单的方法，我们可以把a当作1，b当作2，c当作3……然后
把字符串的所有字符相加，相加结果就是它的hashcode。
bce = 2+3+5 = 10
但是，这个算法虽然简单，却很可能产生hash冲突，比如bce、
bec、cbe的hashcode是一样的

• 转换成26进制数

既然字符串只包含26个小写字母，那么我们可以把每一个字符串当
成一个26进制数来计算。
bce = 2×26
2 + 3×26 + 5 = 1435
这样做的好处是大幅减少了hash冲突，缺点是计算量较大，而且有
可能出现超出整型范围的情况，需要对计算结果进行取模。
因此，选择合适的hashcode是一门学问。为了方便演示，后续我们
采用的是按位相加的哈希（hash）算法

让我们看一个例子吧：

主串通常要比模式串长， 所以正常情况下我们比较主串中与模式串等长的子串才有意义
第一轮 比较主串和模式串的hashcode ： 6 ≠ 12 ，说明模式串和第一个子串不匹配，我们继续下一轮比较。

第二轮： 比较主串和模式串的hashcode ： 9 ≠ 12 ，说明模式串和第二个子串不匹配，我们继续下一轮比较。

这里细心的同学可以发现， 我们并没有直接求取主串中子串的hashcode，而是用第一轮求取的hashcode 减去 子串第一个字符的hashcode然后加上后面的字符的hashcode，这样我们就不需要每次遍历子串中每个字符，降低了时间复杂度

第三轮： 比较主串和模式串的hashcode ： 12 = 12 ，说明模式串和第二个子串匹配，太好了，我们不需要继续比较了。那你就高兴的太早了
俩个字符的hashcode值相等并不就说明这俩个字符串就一定相等

字符串A： b c d 的hashcode值是 2 + 3 + 4 = 9
字符串B： a c e 的hashcode值是 1 + 3 + 5 = 9
这个就叫做哈希冲突

所以最后我们还需要将俩个字符串进行逐个比较，最后才能判断这俩个字符串是否真的匹配
比较之后得出结论，模式串bce是主串abbcefgh的子串，第一次出现的下标是2

代码实现

@SuppressWarnings("all")
public class Main {
    public static int rabinKarp(String str, String pattern) {
        int m = str.length(); 
        int n = pattern.length();
        //计算主串第一个与模式串长度相等的子串的hashcode
        int strCode = hash(str.substring(0, n)); 
        //计算模式串的hashcode
        int patternCode = hash(pattern);
        //如果hashcode相等且字符串匹配则返回位置，要么计算下一位位置hashcode
        for (int i = 0; i < m - n + 1; i++) {
            if ((strCode == patternCode) && compareString(i, str, pattern))
                return i;
            if (i < (m - n)) 
                strCode = nextHash(str, strCode, i, n);
        }
        return -1;
    }
    private static int hash(String str) {
        int hashcode = 0;
        for (int i = 0; i < str.length(); i++) {
            hashcode += str.charAt(i) - 'a';
        }
        return hashcode;
    }
    private static int nextHash(String str, int hash, int index, int n) {
        hash -= str.charAt(index) - 'a';
        hash += str.charAt(index + n) - 'a';
        return hash;
    }
    private static boolean compareString(int i, String str, String pattern) {
        String strSub = str.substring(i, i + pattern.length());
        return strSub.equals(pattern);
    }
    public static void main(String[] args) {
        String str = "abcdef";
        String pattern = "cde";
        int num = rabinKarp(str, pattern);
        System.out.println(num);
    }
}
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

RK算法计算模式串的hashcode需要访问n个字符，计算第一个子串的hashcode也需要访问n个字符，后续子串的hashcode是增量计算，有m-n次，所以总的时间复杂度是O(m+n)。

RK算法的缺点在于哈希冲突。每一次出现哈希冲突的时候，RK算法都要对子串和模式串进行逐个字符的比较，如果冲突太多，RK算法就退化成了BF算法。那么我们还有更高效，更稳定的字符串匹配算法吗？ 那当然，就让我们一起来看看吧

1.3 KMP算法

回顾我们之前的暴力解法

假设主串A的长度是m， 模式串B的长度是n，
主串A:    aaaaaaaaaab
模式串B: aaab
第一轮匹配不成功， 进行第二次比较
主串A:    aaaaaaaaaab
模式串B:   aaab
第二轮匹配不成功， 进行第三次比较
主串A:    aaaaaaaaaab
模式串B:     aaab
…
依次类推
最终
主串A:    aaaaaaaaaab
模式串B:              aaab

从中可以看出，第2轮、第3轮以及后面好几轮的比较都是没有意义的，因为两部分的首字符就已经不匹配了，可是BF算法仍然死板地一位一位挪动和比较，严重影响了算法执行的效率。
那么，我们能否仍然采用字符串比较的思路，并且尽量减少无谓的比较呢？这就涉及我们今天的主角，KMP算法。
大家第一次看看不懂不要怀疑自己，我当初看了一下午，然后花了一下午加一晚上写了这篇题解，大家慢慢看<__>
KMP算法原理

KMP算法提高效率的关键，是对已匹配前缀的有效利用。下面我们来仔细讲一下KMP算法的思路。
让我们来看一个例子：

首先，我们把主串和模式串的首位对齐，从左到右逐个对字符进行比较。
第一轮：模式串和主串的第一个等长子串比较，发现前2个字符都是匹配的，第3个字符不匹配

前面已经匹配上的部分a b a b，我们称之为“已匹配前缀”。
后面不匹配的字符我们称之为“”坏字符“”。
我们可以发现，在已匹配前缀“a b a b ”当中，后俩个字符“a b”和前俩个字符“a b”是相同的。
在下一轮比较时，只有把这两个相同的片段对齐，才有可能出现匹配。这两个字符串片段，分别叫作最长可匹配后缀子串和最长可匹配前缀子串：
第二轮：我们直接把模式串向后移动两位，让两个“a b”对齐，继续从刚才主串的坏字符a开始进行比较： 匹配成功

以上就是KMP算法的整体思路：在已匹配的前缀当中寻找到最长可匹配后缀子串和最长可匹配前缀子串，在下一轮直接把两者对齐，从而实现模式串的快速移动。
接下来我们要解决的就是如何找到一个字符串前缀的“最长可匹配后缀子串”和“最长可匹配前缀子串”

要找到这两个子串，我们事先缓存到一个集合当中，用的时候再去集合里面取。这个集合被称为next数组，next数组到底是什么呢？这是一个一维整型数组，数组的下标代表了“已匹配前缀的下一个位置”，元素的值则是“最长可匹配前缀子串的下一个位置”（也就是最长可匹配前缀子串的长度，因为数组是从0开始计数）。

当模式串的第一个字符就和主串不匹配时，并不存在已匹配前缀子串，更不存在最长可匹配前缀子串。这种情况对应的next数组下标是0，next[0]的元素值也是0。如果已匹配前缀是A、AB，并不存在最长可匹配前缀子串，所以对应的next数组元素值（next[1]，next[2]）同样是0。ABA的最长可匹配前缀是A，对应数组中的next[3]，元素值是1。以此类推，ABAB对应next[4]，元素值是2；ABABA对应next[5]，元素值是3。
有了next数组，我们就可以通过已匹配前缀的下一个位置（坏字符位置），快速寻找到最长可匹配前缀的下一个位置，然后把这两个位置对齐。
比如下面的这种情况，我们通过坏字符下标5，可以找到next[5]=3，即最长可匹配前缀的下一个位置是3

相信大家已经清楚next数组是什么，那大家思考以下怎么生成这个next数组呢？
由于已匹配前缀在主串和模式串当中是相同的，所以我们仅仅依据模式串，就足以生成next数组。
大家非常容易想到：从最长的前缀子串开始，把每一种可能情况都做一次比较。也就是枚举每一种长度的模式串的子串进行比较，假设模式串的长度是n，生成next数组所需的最大总比较次数是1+2+3+4+…+n-1次。

这种效率可想而知是非常低的， 我们可以采用类似“动态规划”的方法，~~ 同学们这时候着急了，我还没学动态规划呢~~
没关系的，只用到了一点非常简单的思想， 同学们没学，几乎也能看懂。 这个思想就是：每一个元素都可以由上一个元素直接或间接推导而来。也就是说已知next[i]的值，如何推导出next[i+1]，也就是求出next[i + 1] 与next[ i] 之间的关系？

在上图中，i所在的位置之前，最长可匹配前缀子串是“ABA”，因此next[i] = 3。那么，next[i+1]和next[i]的关系是什么呢？我们先让i指向下一个字符：

此时，模式串中的字符pattern[i-1]和pattern[j]相同，都是字母”B”，因此最长可匹配前缀子串的长度（j的值）也增加了1：

由此我们可以得出结论1：当下一个字符相同的时候，next[i+1] =next[i] +1。

接下来，我们继续让i指向下一个字符：

此时，模式串中的字符pattern[i-1]和pattern[j]不相同这时候该怎么办呢？我们有一个退而求其次的选择。由于模式串中
有两段曾经的最长可匹配前缀子串（ABAB）是相同的
此时，模式串中的字符pattern[i-1]和pattern[j]不相同，之前的最长可匹配前缀子串也就变得无效了。
我们把问题转化成了在字符串“ABABA”中寻找最长可匹配前缀子串。要想求得“ABABA”的最长可匹配前缀子串，需要由“ABAB”的最长可匹配前缀子串（也就是next[j]）推导出，这就需要我们把指针j进行回溯，回溯到j = next[j]时候的状态
得出结论： 当pattern[i-1]和pattern[j]相同时，next[i+1] = next[i] +1；当pattern[i-1]和pattern[j]不相同时，让j回溯到next[j]，直到j=0无法进一步回溯为止。

大家可能看的云里雾里，为了加深理解， 我们来演示一个完整的next数组填充过程：

当已匹配前缀不存在的时候，最长可匹配前缀子串当然也不存在，所以i=0，j=0，此时next[0] = 0。

接下来，我们让已匹配前缀子串的长度（i）加1：

此时的已匹配前缀是A，由于只有一个字符，同样不存在最长可匹配前缀子串，所以i=1，j=0，next[1] = 0。

我们让已匹配前缀子串的长度继续加1：

此时的已匹配前缀是A B，我们需要开始做判断了：由于模式串当中pattern[j] != pattern[i-1]，即A！= B，最长可匹配前缀子串仍然不存在。（变量j原本就是0，无法回溯。）当i=2时，j仍然是0，next[2] = 0。

接下来，我们让已匹配前缀子串的长度继续加1：

此 时 的 已 匹 配 前 缀 是 ABA ， 由 于 模 式 串 当 中 pattern[j] =pattern[i-1]，即A=A，最长可匹配前缀子串出现了，是A。所以当i=3时，j=1，next[3] = next[2]+1 = 1。

接下来，我们让已匹配前缀子串的长度继续加1

此 时 的 已 匹 配 前 缀 是 ABAB ， 由 于 模 式 串 当 中 pattern[j] =pattern[i-1]，即B=B，最长可匹配前缀子串又增加了一位，是AB。所以当i=4时，j=2，next[4] = next[3]+1 = 2。

接下来，我们让已匹配前缀子串的长度继续加1：

此 时 的 已 匹 配 前 缀 是 ABABA， 由 于 模 式 串 当 中 pattern[j] =pattern[i-1]，即A=A，最长可匹配前缀子串又增加了一位，是ABA。所以当i=5时，j=3，next[5] = next[4]+1 = 3。

接下来，我们让已匹配前缀子串的长度继续加1

此时的已匹配前缀是ABABAC，这时候需要注意了，模式串当中pattern[j] != pattern[i-1]，即B != C，我们需要把变量j回溯到
next[j]，也就是j=1的局面（i值不变）：

回溯后，情况仍然是 pattern[j] != pattern[i-1]，即B!= C。我们继续把变量j回溯到next[j]，也就是j=0的局面：

回溯后，情况仍然是pattern[j] !=pattern[i-1]，即A!=C。j已经不能再次回溯了，所以我们得出结论：i=6时，j=0，next[6]=0。
就这样，完整的next数组就生成了。

最后，让我们梳理一下KMP算法： 我们得到一个next数组， 这是一个一维整型数组，数组的下标代表了“已匹配前缀的下一个位置”，元素的值则是“最长可匹配前缀子串的下一个位置”（也就是最长可匹配前缀子串的长度，因为数组是从0开始计数）。在已匹配的前缀当中寻找到最长可匹配后缀子串和最长可匹配前缀子串，在下一轮直接把两者对齐，从而实现模式串的快速移动。

算法实现

@SuppressWarnings("all")
public class Main1 {
    private  static  int[] getNexts(String pattern) {
        int[] next = new int[pattern.length()];
        int j = 0;

        for (int i = 2; i < pattern.length() ; i++) {
            while ((j != 0) && (pattern.charAt(j) != pattern.charAt(i - 1))) {
                j = next[j];
            }
            if (pattern.charAt(j) == pattern.charAt(i - 1)) {
                j ++;
            }
            next[i] = j;

        }
        return next;
    }

    public static int kmp(String str, String pattern) {
        //生成next[]数组
        int[] next = getNexts(pattern);
        int j = 0;
        //遍历主串字符
        //     i
        // ABABABC
        //     j
        // ABABC 遇到坏字符next[j] = 2    00012
        //    i
//        ABABABC
        //    j
        //  ABABC
        for (int i = 0; i < str.length(); i++) {
            while((j > 0) && (str.charAt(i) != pattern.charAt(j))) {
                //遇到坏字符
                j = next[j];
            }
            if (str.charAt(i) == pattern.charAt(j)) {
                j ++;
            }
            if (j == pattern.length()) {
                return i - pattern.length() + 1;
            }
        }
        return -1;
    }
    public static void main(String[] args) {
        String str = "ABABABC";
        String pattern = "ABABC";
        int index = kmp(str, pattern);
        System.out.println(index);
    }
}

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

求next数组的代码实现和kmp主串遍历的代码实现是非常像的，大家可以总结一下，多看几遍

• 空间复杂度: KMP算法开辟的额外空间只有next数组，假设模式串长度是n，那么算法的空间复杂度就是O(n)。
• 时间复杂度: KMP算法包括两部分，第一部分生成next数组，时间复杂度可以估算为O(n)，第二部分的主循环是对主串的遍历，时间复杂度可以估算为O(m)。因此，KMP算法的整体时间复杂度是O(m+n)，其中n是模式串的长度，m是主串长度。