当前位置：首页 > 科技 > 软件

彻底理解字符串匹配KMP算法

来源：责编：时间：2024-07-03 17:18:53 1040观看

导读大家好，我是小风哥，今天简单聊聊字符串匹配kmp算法。字符串匹配是计算机科学中非常基础的操作，给定两个字符串a和b，我们需要判断字符串a是否包含字符串b。图片像你我这样的普通程序员能想到的最简单方法是这样的，用字符串b

大家好，我是小风哥，今天简单聊聊字符串匹配kmp算法。

字符串匹配是计算机科学中非常基础的操作，给定两个字符串a和b，我们需要判断字符串a是否包含字符串b。

图片

像你我这样的普通程序员能想到的最简单方法是这样的，用字符串b不断去匹配每个主串中的子串。

假设给定这样两个字符串：

图片

首先从主串的第一个位置和子串的第一个位置去匹配，我们发现A和B不相同：

图片

因此主串指针后移一位，子串重新从最第一个字符开始匹配。

图片

这时我们发现A和C不同，因此匹配失败。

图片

主串指针回退到第三个字符，子串重新从第一个字符开始匹配。

图片

此时B和A又不同，重复上述过程。

这次成功找到多个相同的字符，但最后一个字符匹配失败：

图片

按照我们的算法，主串指针需要回退到第5个字符重新匹配。

图片

这就是你我这种肉体凡胎能想到的算法，时间复杂度是O(mn)，效率低下的原因当然是主串指针需要回退。

然而有三位大神不是这么想的，它们跳出来凡人的思考方式发明了一种极具创意的算法，由于是三个人同时发现，因此这个算法取了三人名字的首字母，这就是著名的kmp算法。

图片

看到这里相信你就能明白为什么这个算法很难掌握了吧，难是正常的，觉得不难才不正常，如果你能无师自通搞定kmp算法，那么早出生几十年你也能和大师们并驾齐驱供我等凡夫俗子瞻仰。

废话不多说，接下来就让我们领略一下大师的非凡境界。

注意看这个主串指针，大师们思考的第一个问题就是，主串指针是否有必要回退，这是最关键最核心的问题。

图片

让我们回到刚才部分匹配的示例。

主串指针是否需要需要回退呢？我们思考两种可能。

第一种可能，即使能匹配成功，匹配成功的起始位置也在主串指针H及以后，在这种情况下主串指针不需要回退。

图片

第二种可能，匹配成功的起始位置经过主串指针H：

图片

在这种情况下，主串指针之前的两个字符A和B一定是成功匹配了的：此时我们只需要比较主串指针H及以后的位置即可。

图片

只有这么两种可能。

因此可以看到，主串指针根本就没有必要回退。

现在我们知道了主串指针不需要回退，那么子串指针该从哪里开始匹配呢？从头开始吗？

图片

注意看我们刚才提到的第二种可能，匹配成功的起始位置经过主串指针H，在这种情况下，主串指针之前的两个字符A和B一定是成功匹配了的，这意味着什么呢？

图片

这意味着AB是这个字符串的后缀：

图片

AB是这个字符串的前缀：

图片

不要忘了这两个字符串是成功匹配了的：

图片

也就是说这是两个完全相同的字符串，这就意味着AB是成功匹配字符串的相同前后缀。

图片

这样子符串指针也不需要回退到起始位置，而是从共同前后缀的下一个位置开始匹配即可。

图片

而对于部分匹配的子串根本不存在共同前后缀的情况，

图片

我们直接从子串起始位置进行匹配。

图片

可以看到，由于主串指针不回退，这大幅提高了算法的效率。

想要实现这样的算法，关键是怎样计算出部分匹配子串的共同前后缀。

因此我们来到了第二个核心问题。

我们以ABCDAB为例来讲解。

这是长度为1的前后缀，这是长度为2的前后缀，以此类推。

图片

可以看到，在所有的前后缀中，相同前后缀的最大长度是2。

图片

我们记下来。

实际上我们需要把所有子串的相同前后缀都计算出来。

对于ABCDA这个子串来说，相同前后缀长度是1，因为两个A是相同前后缀。

图片

而对于ABCD这个子串来说，相同前后缀的长度是0，也就是没有相同的前后缀。

其它也一样。

这样我们就到了一个数组，通过查找这个数组我们能知道任意子串的共同前后缀长度。

图片

这个数组在很多资料中被称之为next数组。

有了next数组就简单了。

假设此时我们发现两个指针指向的字符不同，接下来只需要简单查找next数组：

图片

发现已匹配部分的相同前后缀长度是2：

图片

因此主指针不动，子串指针移动到相同前后缀的下一个位置继续去匹配即可。

图片

可以看到，只要我们能得到next数组，就可以在线性时间复杂度内解决问题。

这里，我们来到了第三个核心问题，那就是该怎样高效计算出next数组。

假设此时我们已经计算出了这个子串的共同前后缀，也就是长度为n的这两个部分。

图片

接下来计算下一个位置的最长前后缀，我们只需要分别后移两个指针，然后比较字符是否相等，这里有两种可能。

第一种可能是接下来的字符相同，那么这个子串的最长相同前后缀的长度就是n+1。

图片

然后写到next数组即可，这很好理解。

图片

但是如果下一个位置的字符不相等该怎么办呢？

注意接下来是整个算法最核心的，也是最具技巧的地方。

如果接下来的两个字符不相等，那么前面的这部分绝无可能形成最长前后缀。

图片

因此我们只能找一个更短的。

图片

如果能找到一个更短的，这就意味着这两部分会形成一个共同前后缀。

图片

然后我们继续比较下一个字符就可以了，这就回到最初的问题。

那么这两部分相同意味着什么呢？

不要忘了红色部分是我们之前找到一个共同前后缀，也就是说红色部分的子串完全相同。

图片

而现在这两个子串也相同，这就意味着这两个更小的子串其实是红色部分子串的最长前后缀。

图片

不要忘了，此时我们的指针已经来到了这里，前面这部分的next数组已经计算出来了。

图片

通过查next数组，我们可以快速得到更短前后缀的长度。

既然红色部分的长度是n，那么更短前后缀的长度其实就是next[n-1]。

图片

再来看下，红色部分的长度是n，那么更短前后缀的长度是next[n-1]。

也就是这个位置。

图片

这就是计算next数组源代码中n=next[n-1]这句话的含义。

图片

现在我们再来看一遍整个过程。

此时两个字符的长度不等，那么我们只需要简单查一下next[n-1]：

图片

这就是更短的前后缀长度，假设是4。

图片

此时前一个指针回退到位置4，继续比较下一个字符即可。

图片

如果下一个字符相同，那么当前位置next数组的值就是n+1。

而如果下一个字符不相同，我们继续查找next[n-1]，然后前一个指针回退，继续比较下一个位置即可。

图片

这就是完整的kmp算法实现，可以看到整个代码实际上只有30多行。

如果你能在50多年前写出这几行代码，你也能和它们并列，在计算机科学史上会留下你的一笔。

图片

好啦，以上就是本期全部内容。

本文链接：http://www.28at.com/showinfo-26-98552-0.html彻底理解字符串匹配KMP算法

声明：本网页内容旨在传播知识，若有侵权等问题请及时与本网联系，我们将在第一时间删除处理。邮件：2376512515@qq.com

上一篇： Python 串口收发使用与示例教程

下一篇： XLSX插件全面解析：从入门到精通的数据处理神器

标签：

热门焦点

5月iOS设备好评榜：iPhone 14仅排第43？

来到新的一月，安兔兔的各个榜单又重新汇总了数据，像安卓阵营的榜单都有着比较大的变动，不过iOS由于设备的更新换代并没有那么快，所以相对来说变化并不大，特别是iOS好评榜，老款设
三言两语说透设计模式的艺术-单例模式

写在前面单例模式是一种常用的软件设计模式，它所创建的对象只有一个实例，且该实例易于被外界访问。单例对象由于只有一个实例，所以它可以方便地被系统中的其他对象共享，从而减少
分布式系统中的CAP理论，面试必问，你理解了嘛？

对于刚刚接触分布式系统的小伙伴们来说，一提起分布式系统，就感觉高大上，深不可测。而且看了很多书和视频还是一脸懵逼。这篇文章主要使用大白话的方式，带你理解一下分布式系统
Java NIO内存映射文件：提高文件读写效率的优秀实践！

Java的NIO库提供了内存映射文件的支持，它可以将文件映射到内存中，从而可以更快地读取和写入文件数据。本文将对Java内存映射文件进行详细的介绍和演示。内存映射文件概述内存
华为Mate60系列模具曝光：采用硕大圆形后置相机模组+拼接配色方案

据此前多方爆料，今年华为将开始恢复一年双旗舰战略，除上半年推出的P60系列外，往年下半年的Mate系列也将迎来更新，有望在9-10月份带来全新的华为Mate60
iQOO 11S新品发布会

iQOO将在7月4日19:00举行新品发布会，推出杭州亚运会电竞赛事官方用机iQOO 11S。
朋友圈可以修改可见范围了苹果用户可率先体验

近日，iOS用户迎来微信8.0.27正式版更新，除了可更换二维码背景外，还新增了多项实用功能。在新版微信中，朋友圈终于可以修改可见范围，简单来说就是已发布的朋友圈
Windows 11发布，微软一改往常对老机型开放的态度

距离 Windows 11 发布已经过去一周，在过去一周里，很多数码爱好者围绕其对 Android 应用的支持、对老机型的升级问题展开了激烈讨论。与以往不同的是，在这次大
电博会与软博会实现"线下+云端"的双线融合

在本次“电博会”与“软博会”双展会利好条件的加持下，既可以发挥展会拉动人流、信息流、资金流实现快速交互流动的作用，继而推动区域经济良性发展；又可以聚