关于KMP算法(多图详解)_kmp算法时间复杂度为什么是m+n-程序员宅基地

技术标签: 数据结构  

为什么用KMP算法

KMP是一种高效的模式匹配的一种算法
模式匹配,说直白就是找寻子字符串在主字符串的位置

(其实KMP这三个字没啥意义,这算法是3个人研究出来的,取3人名字首字母也就是KMP)

暴利匹配算法

与KMP相对立的一个算法就是暴力匹配算法,逐个字符一一对比
形象地理解就是请添加图片描述
可以看到在这个简短的例子中,当主字符串(以下简称主串)对比到3时,与子字符串(简称子串)不同
那么就要折返到开始位置的下一位
如果主串再长点,对比的字符再离奇点(比如刚好和子串最后一位不同步)那么主串折返的次数会更多

假设主串长度为m,子串长度为n,那么主串要比对m-n+1个字符(除了最后那个长度比子串还短的都要比对)
最晦气的情况是刚好每次都是子串的最后一位不同步,那么每个主串字符都要比对n
最坏情况的时间复杂度将是O(m-n+1)n 即 O(mn-n2+n),实际情况是m远大于n,所以可以简写为O(mn)

KMP算法思路

暴力匹配算法最大的弊端就是要折返匹配
在这里插入图片描述
比如在上图这个例子中,明显看到在比对第4位的时候出现的不同步
暴力匹配就会重新从主串第2位开始与子串匹配
显然当前的前3位是同步的,如果错开一位必然不同步,造成浪费时间
但是
已经匹配前3位还是有信息可以用的,当前计算机已经知道了主串前3位的序列,我们直观感受的话,下一次匹配应该是把主串的第3位和子串的第1位开始匹配
在这里插入图片描述
而不必再去和主串第2位比,这个直观感觉的什么原理呢?
对于已经匹配的子串序列,可以取共同元素的下一位作为下一次匹配的起点
看不懂也没关系,请看下面分析

研究子串

(以下示例图,第一个数列是主串截取)
如果是第5位不同步
我们能直观感受到,第4位和第1位是相同元素,可以作为下次匹配的起点
在这里插入图片描述
如果是第4位不同步
可以看到,第3位于第1位有相同元素,可以作为下次匹配的起点
在这里插入图片描述

如果是第3位不同步,那没办法了,前两位都不同,逐一比较了
在这里插入图片描述
如果是第2位不同步,第一位相同没啥用……同上图

如果是第1位不同步,那肯定是没什么好折腾了,老老实实下一个数字比较吧

回顾刚才的思路,可以发现我们是在找寻当前位置之前的字符的共同点
再精确点,当前比对位置是j,前1~j-1个字符组成字符串s
找寻s的最长相等前后缀以实现对已经匹配好的字符的复用

前缀:包含第一个字符但不包含最后一个
后缀:包含最后一个字符但不包含第一个

比如这个子串在这里插入图片描述
当j=6时,1~5组成的字符串是abaab
最长相等前后缀就是ab,当第6位不同步时,直接跳转到第3位
在这里插入图片描述
这样,主串就不必返回到之前的状态,始终都是子串在自行调节对比位序

那么研究一下这个方案:找寻当前比对字符之前的字符,的最长相等前后缀

前方的字符串 最长相等前后缀 下一个比对位置
abaab ab 3
abaa a 2
aba a 2
ab 1
a 1

可以看到下一个比对位置是最长相等前后缀的长度+1
当比对第一个字符就不同步时,那么主串要向后移一格,我们就记为0,以示意主串后移
那么就得到这么一个数组
在这里插入图片描述

这就是KMP算法中的next数组,用于指示如果当前匹配失败,下次子串比对位置

流程图

在这里插入图片描述

最后一个判断语句,如果是no,那么意味着是i超出了主串长度
也就是这种情况在这里插入图片描述
主串后面无元素了,依然是匹配失败的情况

进一步优化

观察这个子串及其next数组
在这里插入图片描述
可以看到前4位都相同且为a
当第4位不匹配时
在这里插入图片描述
j应该等于next[4]即3
在这里插入图片描述
显然子串的4号位是a,与主串的4号位不同步,那么位于子串3号位的a也必然不同步
同理,当j=2时,也不同步,j继续指向1
那为什么不直接跳转到第一位呢?
所以,在构建好next数组后,还可以进一步优化

对于子串中的相同元素,取位序小的next值作为当前next值
以减少这种不必要的比对
那么新的next数组nextval应该变为
在这里插入图片描述

时间复杂度

主串长度为m,子串长度为n

暴利匹配算法时间复杂度是O(mn)
KMP算法时间复杂度为O(m+n),因为主串没有回退,子串也是近似没有回退
但在一般情况下暴力匹配算法执行时间也近似为O(m+n)毕竟我们寻找的子串大概率是一组无序的字符组成的,而不是有很多重复。
这也是为什么暴力匹配算法沿用至今。其实是懒
请添加图片描述

都看到这里了,留个赞再走呗。

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/makerjack001/article/details/119763841

智能推荐

苹果付费软件18个,最高499元的软件。_ios付费软件推荐-程序员宅基地

文章浏览阅读1.7w次,点赞8次,收藏15次。(苹果锤子三件套)需要的人多的话,我给大家发一个Thor抓{ T子会员}的教程!Thor三件套(抓包工具)●Thor俗称锤子是一款os平台的抓包调试Htp或Htts协议的工具,在众多抓包调试Htp或Htps协议的工具中功能方面相比较完善和稳定,用户可以通过Thor对绝大多数app进行一些项目的调试,或者抓取一些需要的图片、音频、压缩包、下载链接等,从而制作出来的便是Thor过器。●Anubis是一款网络开发调试和HTTP学习的工具,用来调试API或者学习理解HTTP协议,配合hor使用,可以进行日期._ios付费软件推荐

Python零基础教程7——AI辅助编程之我解-程序员宅基地

文章浏览阅读1.3k次,点赞49次,收藏28次。作为Python编程高手,你精通Python语言的各种特性和功能,对编程有着深入的理解和丰富的经验。你熟悉Python的常见应用领域,如数据分析、机器学习、Web开发等,并能根据需求选择合适的库和框架进行开发。作为一名Python编程高手,你的职责是通过编写高效、可靠的Python代码来解决实际问题,帮助他人理解和应用Python编程技术。无论是初学者还是有经验的开发者,你都能够提供专业的指导和建议,分享最佳实践,帮助他们在Python编程的道路上不断进步。那么他就可以准确度很高的还原已有的正确的编程。

python高级进阶_3_ @property 装饰器的意义01_@property 意义-程序员宅基地

文章浏览阅读400次。这个章节大部分人都明白@property 的作用。难道不是把方法转化成属性,可以直接赋值?那我们说说为什么这么做有什么意义呢?先用代码一点点引导。1.避免直接赋值,绕过校验class Student: def __init__(self,name,age): self.name=name self.age=agestu=Student("La..._@property 意义

爬取豆瓣 TOP250 电影排行榜-程序员宅基地

文章浏览阅读3.4k次,点赞3次,收藏21次。很多朋友在看一部电影前都喜欢先找一下网友们对该片的评价。国内的电影评分网站,要数豆瓣最出名。接下来我们将爬取豆瓣至今TOP250的电影的详细信息。豆瓣有专门一个 TOP250 的电影链接 -> https://movie.douban.com/top250首先我们模拟浏览器发送请求,将数据保存为html网页格式,查看返回数据是否正常。import requestsfrom bs4 ...

什么是物联网(IoT)?-程序员宅基地

文章浏览阅读1.1w次,点赞4次,收藏32次。IoT(即物联网)一词是指互联设备的集合网络,以及促进设备与云之间以及设备自身之间通信的技术。由于价格低廉的计算机芯片和高带宽电信的出现,我们现在已有数十亿台设备连接到互联网。也就是说,牙刷、吸尘器、汽车、机器等日常设备可以利用传感器收集数据,智能地为用户服务。 物联网将日常“事物”与互联网相结合。90 年代以来,计算机工程师一直在为日常用品添加传感器和处理器。但是,这项工作最初进展十分缓慢,因为芯片又大又笨重。名为 RFID 标签的低功耗计算机芯片是首个用于跟踪昂贵设备的芯片。随着计算设备尺寸不断缩小,_iot

浏览器多线程和js单线程_浏览器点击事件是单线程吗-程序员宅基地

文章浏览阅读1.4w次,点赞11次,收藏55次。0.前言开发过程中遇到js线程和ui渲染线程互斥问题。导致ui无法正常更新等问题。这些问题的根源就是因为浏览器的多线程和js的单线程引起的。看本篇博客之前,应该充分理解消息队列,事件循环,同步异步任务等概念。 这些概念以前都知道,也了解多线程的概念。但是当遇到问题的时候,这些东西都被抛到脑后,值得深思。1.知识点补充js单线程js运作在浏览器中,是单线程的,js代码始终在一个线程上执行,此线程被称_浏览器点击事件是单线程吗

随便推点

git pull时出现unable to access ‘ ‘:Could not resolve host: github.com_git pull unable to access-程序员宅基地

文章浏览阅读1.3k次。unable to access ' ':Could not resolve host: github.com解决方案转载自:https://blog.csdn.net/weixin_42259631/article/details/82893426在终端输入:sudo vim /etc/resolv.conf在最后一行增加nameserver 8.8.8.8或者nameserver 114.114.114.114即可。..._git pull unable to access

php数组转请求参数,学习猿地-php 数组如何转为url参数-程序员宅基地

文章浏览阅读176次。php数组转为url参数的实现方法:首先创建一个PHP示例文件;然后定义一个数组;最后通过“http_build_query( $array )”方法将数组转为URL参数即可。php 将数组转换网址URL参数$array =array ( 'id' =123, 'name' = 'dopost' );echo http_build_query( $array );//得到结果id=123name=..._php 数组转reqeust

Linux | nslookup详细介绍一下这指令的作用以及用法_nslookup命令的作用和使用方法-程序员宅基地

文章浏览阅读4.3k次。nslookup是一个网络工具,通常用于查询域名系统(DNS)服务器以获取主机名或IP地址相关的信息。它可以用于查找主机名的IP地址,反向查找IP地址的主机名,以及查询DNS记录的其他信息。_nslookup命令的作用和使用方法

lucene、lucene.NET详细使用与优化详解-程序员宅基地

文章浏览阅读1.1k次。2019独角兽企业重金招聘Python工程师标准>>> ..._n n ___': - _* . &; v. 7_ 'v & .

用python和pygame写游戏_用Python和Pygame写游戏-从入门到精通(6)-程序员宅基地

文章浏览阅读138次。掌握了小小的像素,我们可以使用更加复杂一点的东西了,对,就是图像,无数的像素的集合~还记得上次我们为了生成的一张图片,花了无数时间,还好一般游戏不会在游戏的过程中动态生成图像,都是将画好的作为资源封装到游戏中。对2D游戏,图像可能就是一些背景、角色等,而3D游戏则往往是大量的贴图。虽然是基础,这里还是要罗嗦一下,之前说的RBG图像,在游戏中我们往往使用RGBA图像,这个A是alpha,也就是表示透..._pygame 中 screen.set_clip

TCP/IP协议_tcp/ip包内容-程序员宅基地

文章浏览阅读1.6k次。笔记_tcp/ip包内容