动画：七分钟理解什么是KMP算法

今天药忘吃喽~ 2021-11-26 12:02 320阅读 0赞

点击蓝色“五分钟学算法”关注我哟

加个“星标”，一起学算法

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg]

本文是介绍 **什么是** **BF算法**、**KMP算法**、**BM算法** 三部曲之一。

**KMP算法** 内部涉及到的数学原理与知识太多，本文只会对 **KMP算法** 的运行过程、 **部分匹配表** 、**next数组** 进行介绍，如果理解了这三点再去阅读其它有关 **KMP算法** 的文章肯定能有个清晰的认识。

以下的文字描述请结合视频动画来阅读~

### 定义 ###

**K**nuth-**M**orris-**P**ratt 字符串查找算法，简称为 **KMP算法**，常用于在一个文本串 S 内查找一个模式串 P 的出现位置。

这个算法由 Donald Knuth、Vaughan Pratt、James H. Morris 三人于 1977 年联合发表，故取这 3 人的姓氏命名此算法。

是不是感觉 Donald Knuth 这个名字很眼熟？没错，在前面 **这或许是讲解 Knuth 洗牌算法最好的文章** 一文中也出现了他！

**KMP算法** 的操作流程如下：

*  假设现在文本串 S 匹配到 i 位置，模式串 P 匹配到 j 位置
 *  如果 j = -1，或者当前字符匹配成功（即 S\[i\] == P\[j\] ），都令 i++，j++，继续匹配下一个字符；  
    如果 j != -1，且当前字符匹配失败（即 S\[i\] != P\[j\] ），则令 i 不变，j = next\[j\]。此举意味着失配时，模式串 P相对于文本串 S 向右移动了 j - next \[j\] 位
 *  换言之，将模式串 P 失配位置的 next 数组的值对应的模式串 P 的索引位置移动到失配处

### 运行过程 ###

以下图文本串 S 与模式串 P 为例：

![640?wx\_fmt=png][640_wx_fmt_png]

首先，列出模式串 P 的所有子串：

然后，求得每一个子串的所有前缀与后缀。

**前缀** 指除了最后一个字符以外，一个字符串的全部头部组合；**后缀** 指除了第一个字符以外，一个字符串的全部尾部组合。

以第五列为例进行演示。

**前缀**为

**后缀**为

因此，它的前缀后缀的公共元素的最大长度为 **2**。

求得原模式串 P 的子串对应的各个前缀后缀的公共元素的 **最大长度表** 下图。

![640?wx\_fmt=png][640_wx_fmt_png 1]

根据**最大长度表** 去求 **next 数组**：**next 数组相当于“最大长度值” 整体向右移动一位，然后初始值赋为-1**。

![640?wx\_fmt=png][640_wx_fmt_png 2]

好了，获取了 **next 数组** 后，**KMP 算法** 的操作就很清晰了。

将模式串 P 与文本串 S 的字母一个个进行匹配，当失配的时候，模式串向右移动。

![640?wx\_fmt=png][640_wx_fmt_png 3]

怎么移动？

![640?wx\_fmt=png][640_wx_fmt_png 4]

比如模式串的 **b** 与文本串的 **c** 失配了，找出失配处模式串的 **next数组** 里面对应的值，这里为 **0**，然后将索引为 **0** 的位置移动到失配处。

### 后记 ###

市面上好多讲解 **KMP算法** 的文章的写的太混乱了，很多人因此产生了恐惧，这一章目的就是为了能让大家能大概理解 **KMP算法** 的运行过程，不会畏惧 **KMP算法** 。

我也把视频上传到了B站，喜欢在B站学习的小伙伴可以扫描下面的二维码去观看，欢迎点赞收藏投币~

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 1]

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

**本文相关阅读推荐：**

[毕业十年后，我忍不住出了一份程序员的高考试卷][Link 1]

[一道腾讯面试题：厉害了我的杯][Link 2]

[十大经典排序算法动画与解析，看我就够了][Link 3]

[这或许是东半球分析十大排序算法最好的一篇文章][Link 4]

[面试官，我会写二分查找法！对，没有 bug 的那种！][bug]

[看《长安十二时辰》可以了解哪些算法知识][Link 5]

GitHub 标星 3w+，很全面的算法和数据结构知识

![640?wx\_fmt=png][640_wx_fmt_png 5]

[640_wx_fmt_jpeg]: /images/20211126/b025919d4c9b442cbc94d286e551365d.png
[640_wx_fmt_png]: /images/20211126/d0ffdc12f5954fddba810f74f8c95367.png
[640_wx_fmt_png 1]: /images/20211126/94e50a7590ca4dde9be7048881eb686b.png
[640_wx_fmt_png 2]: /images/20211126/e79a620558794946b8ef37dc82c03ea8.png
[640_wx_fmt_png 3]: /images/20211126/16c8d2c9f98b40939da637b48ca09641.png
[640_wx_fmt_png 4]: /images/20211126/8e8c56461c5a41eda9b172e255ccf7d3.png
[640_wx_fmt_jpeg 1]: /images/20211126/1d6447da64f24ad9bd74deb398f5c442.png
[Link 1]: https://blog.csdn.net/dQCFKyQDXYm3F8rB0/article/details/91488249
[Link 2]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484557&idx=1&sn=739d80488fe1169a9c9ca26ecfcdfba6&chksm=fa0e6b0ccd79e21a1c2b0d99db69f6206cddddfe2367742e9de1d7d17ec35a5ce29fa4e30d63&scene=21#wechat_redirect
[Link 3]: https://blog.csdn.net/dQCFKyQDXYm3F8rB0/article/details/87910210
[Link 4]: https://blog.csdn.net/dQCFKyQDXYm3F8rB0/article/details/92825279
[bug]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485240&idx=1&sn=fbccc747b2e8558c6478171709005ff9&chksm=fa0e68b9cd79e1af5ab68d42adea0b24c7d4867069091df9e95b6f20ab57b69c4e38994a36be&scene=21#wechat_redirect
[Link 5]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485904&idx=1&sn=0eae783ce1b7c0383f41d76a269f511e&chksm=fa0e6651cd79ef47d31a0dba6909873974a964e81654cf702e3868da51fa9a695e7b9a383c1a&scene=21#wechat_redirect
[640_wx_fmt_png 5]: /images/20211126/ee50df1c2041469b96a6736ef80872b0.png