应用场景

字符串匹配问题：

有一个字符串 BBC ABCDAB ABABCDABD ，另一个字符串为 ABCDABD

image-20200523160517802

现在要判断 str1 中是否含有 str2，如果有就返回 str1 中首个匹配字母的索引，如果没有，则返回 1

暴力匹配算法

思路

遍历两个字符串：

  1. 若 str1[i] == str2[j]，则 i++、j++，继续匹配下一个字符
  2. 若 str1[i] != str2[j]，则 i = i - j + 1、j = 0，继续进行匹配
  3. 如此循环直至 i > str1.length && j > str2.length

图解

  • 红色代表匹配失败
  • 绿色代表匹配成功
  • 。。。表示以此类推

image-20200523160906606

image-20200523160743609

image-20200523161010707

image-20200523161110178

image-20200523161226656

image-20200523161010707

image-20200523161353704

image-20200523161443152

image-20200523161010707

image-20200523161725460

代码实现

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
    public int violenceMatch(String str1, String str2) {

        char[] s1 = str1.toCharArray();
        char[] s2 = str2.toCharArray();

        int i = 0;      //索引指向s1
        int j = 0;      //索引指向s2
        while (i < s1.length && j < s2.length) {
            if (s1[i] == s2[j]) {   //若匹配上了则继续后移看是否匹配
                i++;
                j++;
            } else {                //若没有匹配上就回溯，再继续后移
                i = i - j + 1;
                j = 0;
            } 
        }

        if (j == s2.length) { 
            return i - j;           //返回匹配上的第一个字符的索引
        } else {
            return -1;
        } 
        
    }
}

分析

使用暴力匹配法匹配字符串，每次匹配失败都需要回溯到开始位置的后一位，其间花费了大量的时间，仔细思考，其实这些开销是不必要的。

image-20200523162040054

看图，字符串一直从 A 匹配到 D ，D 处不匹配，但是前面的 ABCDAB 都已经一一匹配了，故此时将 str2 后移一位结果可想而知也不会匹配

image-20200523162402920

如图，中间后移的五步结果不算都可以知道是不匹配的，那我们干嘛还要去浪费时间一次一次移动呢？

直接从移动到 str1 中的下一个 A 不香嘛！

那我们可以可以设计某种算法来进行优化呢？

我觉得不行

但是有三位聪明的大师做到了！

这种算法被命名为 KMP算法 ，也就是今天的主角了！

KMP算法

简介

  • KMP是三位大牛：D.E.Knuth、J.H.Morris 和 V.R.Pratt 同时发现的。其中第一位就是《计算机程序设计艺术》的作者！

  • KMP算法要解决的问题就是在字符串（也叫主串）中的模式（pattern）定位问题。说简单点就是我们平时常说的关键字搜索。模式串就是关键字，如果它在一个主串中出现，就返回它的具体位置，否则返回-1（常用手段）。

思路

  • KMP算法如何实现呢，这里我们需要先引入一些概念

image-20200523163401092

  • 举例：“ABCDABD”

    • ”A”的前缀和后缀都为空集，共有元素的长度为 0
    • ”AB”的前缀为[A]，后缀为[B]， 共有元素的长度为 0
    • “ABC”的前缀为[A, AB],后缀为[BC, C]，共有元素的长度 0
    • ”ABCD” 的前缀为[A, AB, ABC],后缀为[BCD, CD, D]，共有元素的长度为 0
    • ”ABCDA”的前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA,A]，共有元素为”A”，长度为 1
    • ”ABCDAB”的前缀为[A, AB, ABC, ABCD, ABCDA],后缀为[BCDAB, CDAB, DAB, AB, B],共有元素为”AB”,
      长度为 2
    • ”ABCDABD”的前缀为[A, AB, ABC,ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD,
      D]，共有元素的长度为 0

    通过上述分析，我们可以得到一张部分匹配表

    A B C D A B D
    0 0 0 0 1 2 0

    这张部分匹配表就是 KMP算法的核心，接下来我们就要用它了！

接着暴力匹配算法走：

image-20200523162040054

当 D 与 “ ” 不匹配时，前面六个字符 “ABCDAB” 是匹配的，查 部分匹配表 可知最后一个匹配的字母 B 对应的部分匹配值为 2

由公式：
$$
移动位数 = 已知匹配字符数 - 对应匹配值
$$
可得 移动位数 = 6 - 2 = 4

故将搜索词向后移动 4 位

image-20200523165755165

image-20200523170017335

C 的部分匹配值为 0，

由公式得 位移位数 = 2 - 0 = 2

故将搜索词后移两位

image-20200523170148706

image-20200523161010707

以此类推，可高效得到答案！

至此，KMP算法 思路分析全部结束。

至于原理，emmm，比较玄学的东西还没有学习，可以参考 https://zhuanlan.zhihu.com/p/83334559

代码实现

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
public int kmpSearch(String str1, String str2) {
    
    //部分匹配表
    int[] next = kmpNext(str2);

    for (int i = 0, j = 0; i < str1.length(); i++) {
        while (j > 0 && str1.charAt(i) != str2.charAt(j)) {
            j = next[j - 1];
        }
        if (str1.charAt(i) == str2.charAt(j)) {
            j++;
        }
        if (j == str2.length()) {
            return i - j + 1;
        }
    }
    return -1;
}


public int[] kmpNext(String dest) {

    //创建一个 next 数组来保存部分匹配值
    int[] next = new int[dest.length()];
    //字符串长度为 1 时，部分匹配值为 0
    next[0] = 0;
    for (int i = 1, j = 0; i < dest.length(); i++) {
        while (j > 0 && dest.charAt(i) != dest.charAt(j)) {
            j = next[j - 1];
        }

        if (dest.charAt(i) == dest.charAt(j)) {
            j++;
        }
        next[i] = j;
    }
    return next;
}

mvn install:install-file -DgroupId=com.google.code.kaptcha -DartifactId=kaptcha -Dversion=2.3 -Dfile=E:\CS\Java\Project\ruoyi\kaptcha-2.3.2.jar -Dpackaging=jar -DgeneratePom=true

参考

尚硅谷：https://www.bilibili.com/video/BV1E4411H73v?p=161

labuladong：https://zhuanlan.zhihu.com/p/83334559