七分钟理解什么是 KMP 算法

小灰灰 2023-06-13 09:09 24阅读 0赞

本文是介绍 **什么是** **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 为例：

![v2-2b55e0d16e743339d7773e5dce7cd0e1\_b.jpg][v2-2b55e0d16e743339d7773e5dce7cd0e1_b.jpg]

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

![v2-c0e068b77bd1a372d323fa07548d39f2\_b.jpg][v2-c0e068b77bd1a372d323fa07548d39f2_b.jpg]

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

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

以第五列为例进行演示。

**前缀**为

![v2-b80fdd8855533ed2e0869b4bd785ba8c\_b.jpg][v2-b80fdd8855533ed2e0869b4bd785ba8c_b.jpg]

**后缀**为

![v2-2e98b0563a793c9a81c612fcc06f0614\_b.jpg][v2-2e98b0563a793c9a81c612fcc06f0614_b.jpg]

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

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

![v2-9487d0da9a15f8d130772e39a108c463\_b.jpg][v2-9487d0da9a15f8d130772e39a108c463_b.jpg]

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

![v2-33e5d797cc28897ad750f91e1f460289\_b.jpg][v2-33e5d797cc28897ad750f91e1f460289_b.jpg]

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

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

怎么移动？

![v2-bb9103720faddee43ed9542e3e65d846\_b.jpg][v2-bb9103720faddee43ed9542e3e65d846_b.jpg]

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

![v2-e8440931091c5f07a69c684f962382fc\_b.jpg][v2-e8440931091c5f07a69c684f962382fc_b.jpg]

### 后记 ###

如果大家看这一章能大概理解 **KMP算法** 的运行过程的话，那么后续对 **KMP算法** 的更深入讲解，比如代码实现、next数组优化、时间复杂度分析等知识点肯定也是理解的。

**我的专栏：**

[和程序员小吴一起学算法][Link 1]

**❤️ 看完三件事：**

如果你觉得这篇内容对你挺有启发，我想邀请你帮我三个忙：

1.  **点赞，**让更多的人也能看到这篇内容（**收藏不点赞，都是耍流氓 -\_-**）
2.  **关注我和专栏，**让我们成为长期关系
3.  **关注公众号「五分钟学算法」，**第一时间阅读最新的算法文章，公众号后台回复 1024 送你 50 本 算法编程书籍。

![v2-54b27f672009f4d799ff24debc557899\_b.jpg][v2-54b27f672009f4d799ff24debc557899_b.jpg]

[v2-2b55e0d16e743339d7773e5dce7cd0e1_b.jpg]: https://img-blog.csdnimg.cn/img_convert/64486f00d93542f01aeedb21eb595beb.png
[v2-c0e068b77bd1a372d323fa07548d39f2_b.jpg]: https://img-blog.csdnimg.cn/img_convert/21ac65a35df63f2efb12a83c2dcbc52a.png
[v2-b80fdd8855533ed2e0869b4bd785ba8c_b.jpg]: https://img-blog.csdnimg.cn/img_convert/110d752b99dad976128a3667015af08c.png
[v2-2e98b0563a793c9a81c612fcc06f0614_b.jpg]: https://img-blog.csdnimg.cn/img_convert/efb18152ff1300ca9a0f211b3e40d3da.png
[v2-9487d0da9a15f8d130772e39a108c463_b.jpg]: https://img-blog.csdnimg.cn/img_convert/9140883c6e3688a9ecdb7b534f286819.png
[v2-33e5d797cc28897ad750f91e1f460289_b.jpg]: https://img-blog.csdnimg.cn/img_convert/47d6c4d190d967b714cb5ac5104f2227.png
[v2-bb9103720faddee43ed9542e3e65d846_b.jpg]: https://img-blog.csdnimg.cn/img_convert/99b54df561b7dfc9aa0be577c09d144e.png
[v2-e8440931091c5f07a69c684f962382fc_b.jpg]: https://img-blog.csdnimg.cn/img_convert/beb6a4c42f33f743c4060a875678428c.png
[Link 1]: https://zhuanlan.zhihu.com/c_1039097450233057280
[v2-54b27f672009f4d799ff24debc557899_b.jpg]: https://img-blog.csdnimg.cn/img_convert/52f2b6f42447a05a4d6173c38129b9aa.png