图解算法：KMP算法

比眉伴天荒 2022-11-13 05:20 167阅读 0赞

### 目录 ###

*  第一章 暴力匹配实现
 *  第二章 KMP算法介绍
 *  第三章 KMP算法原理
 *  第四章 KMP的匹配表
 *  第五章 KMP算法实现

--------------------

> 项目地址：https://gitee.com/caochenlei/algorithms

# 第一章 暴力匹配实现 #

【问题描述】

有一个字符串 str1 = “BBC ABCDAB ABCDABCDABDE”，和一个子串 str2 = “ABCDABD”，现在要判断 str1 是否含有 str2，如果存在，就返回第一次出现的位置，如果不存在，就返回-1。

【问题思路】

![4393ffad805b178b36e40c2f98b2dfb1.png][]

【代码实现】

public class ViolentMatch { 
        public static void main(String[] args) { 
            String str1 = "BBC ABCDAB ABCDABCDABDE";
            String str2 = "ABCDABD";
            System.out.println(violentMatch(str1, str2));
        }
    
        public static int violentMatch(String str1, String str2) { 
            char[] ch1 = str1.toCharArray();//转换为对应字符数组
            char[] ch2 = str2.toCharArray();//转换为对应字符数组
    
            int i = 0;//指向ch1的下标
            int j = 0;//指向ch2的下标
    
            while (i < ch1.length && j < ch2.length) { 
                //当前字符匹配成功
                if (ch1[i] == ch2[j]) { 
                    i++;
                    j++;
                }
                //当前字符匹配失败
                else { 
                    i = i - j + 1;
                    j = 0;
                }
            }
    
            //判断是否匹配成功
            if (j == ch2.length) { 
                return i - j;
            } else { 
                return -1;
            }
        }
    }

【代码运行】

# 第二章 KMP算法介绍 #

KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称他为克努特—莫里斯—普拉特操作（简称KMP算法）。KMP算法的核心是利用匹配失败后的信息，尽量减模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息，KMP算法的时间复杂度`O(m+n)`，而使用暴力匹配的时间复杂度则是`O(mn)`。

# 第三章 KMP算法原理 #

举例来说，有一个字符串 Str1 = “BBC ABCDAB ABCDABCDABDE”，判断里面是否包含另一个字符串 Str2 = “ABCDABD”？

1、首先，用Str1的第一个字符和Str2的第一个字符去比较，不符合，关键词向后移动一位。

![6980c4744c55ff414b06ed383a23f18f.png][]

2、重复第一步，还是不符合，再后移。

![47748963d2006045c0573a3071325864.png][]

3、一直重复，直到Str1有一个字符与Str2的第一个字符符合为止。

![3174076550647cfbe4d70295a45491dd.png][]

4、接着比较字符串和搜索词的下一个字符，还是符合。

![8c9eca01c8a835784fafb113d4151d19.png][]

5、遇到Str1有一个字符与Str2对应的字符不符合。

![1f5705a56f2eb2568888efeb277a241b.png][]

6、这时候想到的是继续遍历Str1的下一个字符，重复第1步。

![f87b3b54e65db69bc50287bc35310afc.png][]

7、其实这是很不明智的，因为此时”ABCDAB”已经比较过了，没有必要再做重复的工作，一个基本事实是，当空格与D不匹配时，你其实知道前面六个字符是”ABCDAB”。KMP算法的想法是，设法利用这个已知信息，不要把”搜索位置“移回已经比较过的位置，继续把他向后移，这样就提高了效率。怎么做到把刚刚重复的步骤省略掉？可以对Str2计算出一张《匹配表》，这张表的产生在后面介绍。

![2d03de5e3711db249411954e2728816f.png][]

8、已知空格与D不匹配时，前面六个字符”ABCDAB”是匹配的。查表可知，最后一个匹配字符B对应的”部分匹配值”为2，因此我们只需要让模式串Str2的下标移动到对应下标为2的位置，也就是C，此时Str1的下标还是保持不变，在空格处，这样就避免了Str1下标回溯到第6步了，这样就大大减少了Str1的比较次数。

![59595734ba8baa2860c957523b56b8c2.png][]

9、因为空格与Ｃ不匹配，搜索词还要继续往后移。这时已匹配的字符串为”AB”，最后一个匹配字符B对应的”部分匹配值”为0。因此我们只需要让模式串Str2的下标移动到对应下标为0的位置，也就是A，此时Str1的下标还是保持不变。

![6a8dcd32a63e419c6e25c894f43ae557.png][]

10、因为空格与A不匹配，并且此时并没有匹配的字符，因此只能继续后移一位。

![71b48bd4da63d2b714b37912f82a0682.png][]

11、然后逐位比较，直到发现C与D不匹配。

![5c67a882141f483269b098cf97fc5211.png][]

12、因为C与D不匹配，这时已匹配的字符串为”ABCDAB”，最后一个匹配字符B对应的”部分匹配值”为2。因此我们只需要让模式串Str2的下标移动到对应下标为2的位置，也就是C，此时Str1的下标还是保持不变。

![fdeff0138a6369f6a541300c642d784d.png][]

13、然后逐位比较，直到搜索词的最后一位，发现完全匹配，于是搜索完成。

![6da4a82a74a6474ef017ebaff85db1d6.png][]

# 第四章 KMP的匹配表 #

介绍匹配表如何产生之前，我们首先介绍什么是前缀什么是后缀？

*  什么是前缀：包含首字母但不包含尾字母的所有子串。
 *  什么是后缀：包含尾字母但不包含首字母的所有子串。

这里以模式串“ABCAB”为例，该模式串的前缀和后缀依次如下图：

![feb724fae835a3a0afc94861a9d4f6a8.png][]

那么模式串“ABCAB”的匹配值就是 **前缀和后缀最大相同子串的长度** ：AB（2）

接下来，我们以模式串“ABCAB”为例，逐步获取该模式串的匹配表：

*  A：匹配值为0
 *  AB：匹配值为0
 *  ABC：匹配值为0
 *  ABCA：匹配值为1
 *  ABCAB：匹配值为2

通过逐步分解模式串“ABCAB”，将每个子串的匹配值转化为匹配表：

![a7f12319915227fc47c7856bbf9faead.png][]

# 第五章 KMP算法实现 #

【视频推荐】

1.  帮你把KMP算法学个通透！（理论篇），访问地址：https://www.bilibili.com/video/BV1PD4y1o7nd
2.  帮你把KMP算法学个通透！（代码篇），访问地址：https://www.bilibili.com/video/BV1M5411j7Xx

【代码实现】

public class KMPMatch { 
        public static void main(String[] args) { 
            String str1 = "BBC ABCDAB ABCDABCDABDE";
            String str2 = "ABCDABD";
            System.out.println(kmpMatch(str1, str2));
        }
    
        //KMP匹配表
        public static int[] kmpNext(String str2) { 
            int[] next = new int[str2.length()];
            for (int i = 1, j = 0; i < str2.length(); i++) { 
                //然后再考虑不相等的情况2
                while (j > 0 && str2.charAt(i) != str2.charAt(j)) { 
                    j = next[j - 1];
                }
                //写代码先考虑相等的情况1
                if (str2.charAt(i) == str2.charAt(j)) { 
                    j++;
                }
                next[i] = j;
            }
            return next;
        }
    
        //KMP匹配法
        public static int kmpMatch(String str1, String str2) { 
            int[] next = kmpNext(str2);
            for (int i = 0, j = 0; i < str1.length(); i++) { 
                //然后再考虑不相等的情况2
                while (j > 0 && str1.charAt(i) != str2.charAt(j)) { 
                    j = next[j - 1];
                }
                //写代码先考虑相等的情况1
                if (str1.charAt(i) == str2.charAt(j)) { 
                    j++;
                }
                if (j == str2.length()) { 
                    return i - j + 1;
                }
            }
            return -1;
        }
    }

【代码运行】

[4393ffad805b178b36e40c2f98b2dfb1.png]: /images/20221022/7d1d3f1d15484d74b2b3417cc8bf6682.png
[6980c4744c55ff414b06ed383a23f18f.png]: /images/20221022/fb98c862377a4dff9780bc51059636f6.png
[47748963d2006045c0573a3071325864.png]: /images/20221022/bbee10a6ad4e40aea49d2be2b53d2bdf.png
[3174076550647cfbe4d70295a45491dd.png]: /images/20221022/569f5a0f05064b04856379f1e2a5a6aa.png
[8c9eca01c8a835784fafb113d4151d19.png]: /images/20221022/0453457966704937a348407938fb9e01.png
[1f5705a56f2eb2568888efeb277a241b.png]: /images/20221022/76dbc1a765b84f5aafb87d3d5232ae64.png
[f87b3b54e65db69bc50287bc35310afc.png]: /images/20221022/3179e83d39ec4e3386a00b930ede2160.png
[2d03de5e3711db249411954e2728816f.png]: /images/20221022/5bbbe56e0b964aa49b065eb20aa944b0.png
[59595734ba8baa2860c957523b56b8c2.png]: /images/20221022/cb153afc485b4de0ae0ef2889ea59bb1.png
[6a8dcd32a63e419c6e25c894f43ae557.png]: /images/20221022/93fd9e521c744b8d9236a2f41c0ceadb.png
[71b48bd4da63d2b714b37912f82a0682.png]: /images/20221022/95b030f543ca4c759b9dfb098b7bbc1f.png
[5c67a882141f483269b098cf97fc5211.png]: /images/20221022/75cca5e8a1cf47dcbdbc1e4f344318f3.png
[fdeff0138a6369f6a541300c642d784d.png]: /images/20221022/f72f89bb52704e21a1887e357acd384d.png
[6da4a82a74a6474ef017ebaff85db1d6.png]: /images/20221022/eeeb17f0253a496a9680dc03ca3bff40.png
[feb724fae835a3a0afc94861a9d4f6a8.png]: /images/20221022/e11005472e61477c92406b09c5990981.png
[a7f12319915227fc47c7856bbf9faead.png]: https://img-blog.csdnimg.cn/img_convert/a7f12319915227fc47c7856bbf9faead.png