用动画给面试官解释 KMP 算法

Bertha 。 2023-07-15 02:46 1阅读 0赞

点击上方蓝字设为星标![format_png][]

下面开始今天的学习～

![format_png 1][]

作者 | 小鹿

来源 | 小鹿动画学编程

什么是 KMP？

![format_png 2][]

听说 KMP 算法是一种字符串的改进算法，嗯~ 字符串匹配算法还有啥？不好意思，记性不好，居然忘记了。咱们继续，KMP 算法是由D.E.Knuth，J.H.Morris 和 V.R.Pratt 发明的，至于名字怎么读，四级没过，反正我不认识。

这都不重要，重要的是 KMP 算法的核心，它是主要利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。

嗯~ 听起来比暴力破解法牛逼的多，至于如果快速匹配的，还需要深入研究一下。

KMP的由来？

![format_png 2][]

在一个夜黑风高的夜晚，我翻看了全网的 KMP ，读了一遍又一遍，还是看不懂，不知吃了多少碗泡面之后，突然灵感来了，

我快速打开编辑器，写下了两行测试字符。

![format_png 3][]

如果由以上模式串和子串，子串要在模式串中做一个字符串匹配，一般的匹配过程如下：

![format_png 4][]

当我们遇到最后一个字符匹配 E 与 D 并不能完全匹配，那么我们开始往后移动子串一个，一个个重新进行比较。

![format_png 5][]

然而发现第一个字符就不能匹配成功，那好吧，继续往后移动子串。

直到移动到下面这种情况，虽然匹配了 A 和 B，但是到了第三个字符，E 和 C 又不能匹配了，真伤心，好不容易匹配成功前两个。

![format_png 6][]

通过以上，我们发现暴力匹配，就算前几个已经匹配成功，但是由于最后匹配失败导致了重新移动一位，这也太浪费时间了。

既然我们知道前几位匹配的信息。比如第一次匹配，我们知道了已经成功匹配了 ABCAB 了。能不能利用已经知道的匹配信息进行析，然后一次性往后移动多位呢？

KMP 原理

![format_png 2][]

实话告诉你，没有。但是这几个人做到了，分别是 K 某，M 某，P某的三个人，不愧是大佬中的传奇人物，我就咋没想到呢？这次又被石锤智商低下了。

但是我们想象能力还是挺强的，假如有一个神奇的“表”，我们暂且起名叫做匹配表吧，那么我们每次移动的次数，这个神奇的表能够告诉我们，我们岂不是美滋滋的往后移动多位进行快速匹配不就可以了吗？

尼玛尼玛哄，你骂谁呢？不好意思，错了，重来，玛尼玛尼哄，这张神奇的匹配表说来就来。

![format_png 7][]

虽然这个表目前是幻想出来的，无关紧要，我们再试着匹配一次上边用到的字符串。

![format_png 3][]

开始正式匹配，匹配到 E 和 D 就卡壳了，既然有了神奇的匹配表，不需要一个个的移动了，我们应该问一下神奇的“表”，魔表魔表，下一步应该把子串移动多少位？

![format_png 8][]

此时匹配表进行疯狂的计算，对于如何计算，也告诉我们公式了。它来询问你，这才字符匹配成功匹配了几个字符，很容易在图中得到，ABCAB 共 5 位匹配成功。

然后又问，这五位中最后一位是谁？当然是 B 了，那么 B 在匹配表中的匹配值是多少？稍等，我看看匹配表哈~ 嗯~ 这个 B 对应的是 1。

好了，用成功匹配的位数减去匹配值就是下一次要移动的次数。

纳尼？这么神奇？然后我就傻了吧唧相信了去试了试，测试过程如下。

![format_png 9][]

嗯~ 5 - 2 等于 3，所以我要将子串移动四位，如下图位置。

![format_png 10][]

然后我再进行匹配，当遇到 E 与 C 的时候，匹配失败，此时已经匹配了两个元素，分别为 AB，那下一次要往后移动多少呢？

![format_png 6][]

还是按照上边的方式计算，已匹配 2 的字符，此时已匹配字符 AB 最后一个字符是 B，所以这个 B 对应的匹配表的匹配值为0，往后移动 2-0等于 2，往后移动两位。

![format_png 11][]

继续匹配，发现第一个字符就匹配失败了，继续移动一位，最后发现全匹配。

![format_png 12][]

整体的 KMP 算法就是这么一个思路，但是我们所用到的这个匹配表示我们想象出来的，能不能计算出来呢？理想总是很美好，但现实很骨感。

![format_png 13][]

计算匹配表

![format_png 2][]

首先要弄懂两个概念，就是前缀和后缀的概念。

对于我们的子串来说，它的前缀有哪些呢？对于前缀就是除了最后个字符以外所有的顺序组合方式。比如 A、AB、ABC、ABCA、ABCAB。

后缀正好相反，除了第一个字符外，其他所有的组合方式。比如BCABD、CABD、ABD、ABD、BD、D。

![format_png 14][]

对于每个匹配值是如何计算的，那就对子串的每个字符组合寻找出前缀和后缀，然后进行比较是否有相同的，相同的字符组合有几位，就是所谓的匹配值。

这样纯文字说可能很懵逼，直接上图。

![format_png 15][]

我们可以在图中发现，并没有对子串移动的规律发现任何问题，但是我们在看一下子串。

![format_png 16][]

突然恍然大悟，从上图中发现有时候在同一字符串中出现两种相同的字符，比如上图中的 AB，由两个字符组成的，所以匹配值为 2，同时在匹配的过程中，如果 D 前边的字符能够匹配，则子串往后移动 3 位，则再次匹配 AB，原来这是 KMP 的精髓所在。

推荐阅读：
    五分钟学算法：动手写一个双向链表
    
    当初我要是这么学习「进程和线程」就好了（附带思维导图）
    
    当初我要是这么学习操作系统就好了（附带思维导图）
    
    啥是布隆过滤器算法？

[format_png]: /images/20230529/db0e740d00d84b308ed71e7896f94880.png
[format_png 1]: /images/20230529/da836cc371b4403282904c77a675ca38.png
[format_png 2]: /images/20230529/20cc0447a68241d88f368cd369b4ff1b.png
[format_png 3]: /images/20230529/7311b6d0bc5243488b97bdb01dd0acd2.png
[format_png 4]: /images/20230529/7aa4282e703d4aa3bb27dbb0772c2778.png
[format_png 5]: /images/20230529/52f73114ac354150999e55e3d8923898.png
[format_png 6]: /images/20230529/8e1b7c94e9ac4788b7f4f9262d54f49e.png
[format_png 7]: /images/20230529/32b26a37cc6d4ea8a33eadabcc382ec3.png
[format_png 8]: /images/20230529/436b8cbd5bcf4b628edcc15f0795c5c9.png
[format_png 9]: /images/20230529/896ad189c1624336bdf0c0fc6d3081e4.png
[format_png 10]: /images/20230529/904c8630899446559df7c1dc1be3f202.png
[format_png 11]: /images/20230529/5f4b7b9c6ba74a53a860f77f374c8689.png
[format_png 12]: /images/20230529/87b66144d93b4ed78d76458522cbeee8.png
[format_png 13]: /images/20230529/49299e28d5ab47d6b1b454b589772a7b.png
[format_png 14]: /images/20230529/e721c722c0924f49ad009335a81132d5.png
[format_png 15]: /images/20230529/d160d6825ee84707b99e1b8488c9a36f.png
[format_png 16]: /images/20230529/fce5207849cf419c8a98f05b33d634a6.png