如何理解kmp的套娃式算法啊?

概念

KMP算法,全称Knuth Morris Pratt算法 。文章大部分内容出自《数据结构与算法之美》

核心思想

假设主串是a,模式串是b

在模式串与主串匹配的过程中,当遇到不可匹配的字符的时候,对已经对比过的字符,是否能找到一种规律,将模式串一次性滑动多位,跳过那些肯定不会匹配的情况?

在这里插入图片描述

这里可以类比一下,在模式串和主串匹配的过程中,把不能匹配的那个字符仍然叫做坏字符,把已经匹配的那段字符串叫做好前缀

在这里插入图片描述
当遇到坏字符的时候,就要把模式串往后滑动,在滑动的过程中,只要模式串和好前缀有上下重合,前面几个字符比较,就相当于拿好前缀的后缀子串,跟模式串的前缀子串在比较

KMP目的

在这里插入图片描述
只需要拿好前缀本身,在它的后缀子串中,查找最长的那个可以跟好前缀匹的前缀子串匹配

假设最长的可匹配的那部分前缀子串{v}, 长度为k

可以把模式串一次性往后滑动j - k位,相当于,每次遇到坏字符的时候,就把j 更新为k。i不变。然后比较

最长可匹配后缀子串 && 最长可匹配前缀子串

把好前缀的所有后缀子串中,最长的可匹配前缀子串的那个后缀子串,叫作最长可匹配后缀子串

对应的前缀子串,叫作最长可匹配前缀子串

在这里插入图片描述
为什么求最长可匹配子串前缀和后缀子串,为什么不涉及主串,只需通过模式串就能求解?

以上图所示,好前缀的定义是主串和模式串匹配的部分
所以好后缀的最长可匹配子串必然会落到模式串中,所以用模式串求最长可匹配的前缀和后缀子串

失效函数(next 数组)

在这里插入图片描述
数组的下标是每个前缀结尾字符下标,数组的值是这个

前缀的最长可以匹配前缀子串的结尾字符下标

例子:ababacd

  • 前缀列表访问顺序:从右到左
  • 后缀列表访问顺序:从左到右
    过程
1. a: 无匹配,下标为-1
2. ab: 无匹配,下标为-1
3. aba: 匹配1个字符。下标为0前缀: a ab后缀: ba a
4. abab,匹配2个字符,下标为1前缀:a ab aba后缀:bab ab b
5. ababa,匹配3个字符,下标为2前缀:a ab aba abab后缀:baba aba ab a
6. ababac,无匹配,下标为-1前缀:a ab aba abab ababa后缀:babac abac bac ac c
7. ababacd,无匹配,下标为-1前缀:a ab aba abab ababa ababac后缀:babacd abacd bacd acd cd c

next数组的计算

暴力计算方法

暴力求解子串,效率低
在这里插入图片描述
把所有后缀子串从长到短找出来,依次看能否匹配前缀

类动态规划方法(k:最长前后缀子串)

若p[k] == p[i]

在这里插入图片描述
如果 next[i - 1] = k - 1,那么子串 b[0, k - 1] 是 b[0, i - 1]最长可匹配前缀子串

如果子串 b[0, k - 1] 的下一个字符 b[k],与 b[0, i -1 ]的下一个字符 b[i] 匹配,那子串 b[0, k]就是 b[0, i]的最长可匹配前缀子串

若p[k] ≠ p[i]

假设最长可匹配前缀 k

如果 p[k] ≠ p[i]。则需要次最大匹配前缀 p[next[k]].

如果 p[next[k]] ≠ p[i]. 则需要次次最大匹配前缀。直到匹配成功,或者匹配失败
在这里插入图片描述
在这里插入图片描述

代码地址

数据结构和算法

时间复杂度

构建next数组

void getNext(char *p, int p_len, int *next) {next[0] = -1;int k = -1;int i;for (i = 1; i < p_len; ++i) {while (k != -1 && p[k + 1] != p[i]) {k = next[k];}if (p[k + 1] == p[i]) {++k;}next[i] = k;}}

i 从1开始一直增加到p_len,而k并不是每次for循环都增加,所以,k累积增加的值肯定小于 p_len

而while循环中的 k = next[k],实际上是在减小k的值,k累积都没有增加超过p_len.所以while循环总数也不会超过p_len

这部分时间复杂度: O(p_len)

借助next数组匹配

int kmp(char *s, int s_len, char *p, int p_len) {int next[p_len];getNext(p, p_len, next);int j = 0;int i;for (i = 0; i < s_len; ++i) {while (j > 0 && s[i] != p[j]) { // 一直找到s[i] 和 p[j]j = next[j - 1] + 1;}if (s[i] == p[j]) ++j;if (j == p_len) {   // 找到匹配模式串return i - p_len + 1;}}return -1;
}

i 从0循环增加到 s_len - 1, j的增长量不可能超过i,所以肯定小于s_len

而while 循环中的那条 j = next[j - 1] + 1; 不会让 j增长

所以,这部分的时间复杂度为O(s_len)

总时间复杂度: O(s_len + p_len)

空间复杂度

KMP只需要一个额外的next数组,数组的大小跟模式串相同

空间复杂度:O(p_len), p_len表示模式串长度

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/329225.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

开源大模型与闭源大模型:技术哲学的较量

目录 前言一、 开源大模型的优势1. 社区支持与合作1.1 全球协作网络1.2 快速迭代与创新1.3 共享最佳实践 2. 透明性与可信赖性2.1 审计与验证2.2 减少偏见与错误2.3 安全性提升 3. 低成本与易访问性3.1 降低研发成本3.2 易于定制化3.3 教育资源丰富 4. 促进标准化5. 推动技术进…

【数学】泰勒公式

目录 引言 一、泰勒公式 1.泰勒公式及推导 &#xff08;1&#xff09;推导 &#xff08;2&#xff09;公式 2.泰勒中值定理 &#xff08;1&#xff09;定理1&#xff08;佩亚诺余项&#xff09; &#xff08;2&#xff09;定理2&#xff08;拉格朗日余项&#xff09; …

pdf文件怎么编辑?分享3个专业的pdf软件!

在数字化时代&#xff0c;PDF文件已成为我们工作、学习中的得力助手。然而&#xff0c;面对需要修改的PDF文件&#xff0c;许多人却感到无从下手。今天&#xff0c;就让我们一起探索如何轻松编辑PDF文件&#xff0c;并介绍几款实用的编辑软件&#xff0c;让你轻松应对各种PDF编…

高中数学:平面向量-数量积(向量与向量的乘积)与投影

一、引题 物理上的力做功 二、数量积与投影 1、数量积 θ的范围是[0,π] 2、投影 向量的投影&#xff0c;依然是一个向量&#xff01; 3、运算法则 易错点&#xff1a; 4、重要性质 这里对性质(2)要注意一下&#xff1a;如果 a → \mathop{a}\limits ^{\rightarrow…

【Linux】Centos7安装JDK

【Linux】Centos7安装JDK 下载 Oracle 官网下载 JDK17 https://www.oracle.com/cn/java/technologies/downloads/#java17 安装 使用rz命令上传 jdk tar 包&#xff0c;上传失败直接用 xftp 上传 在安装图形界面时&#xff0c;有勾选开发工具&#xff0c;会自动安装 JDK 需要先…

白鲸开源CEO郭炜在2024 DataOps发展大会上获聘专家

2024年5月15日&#xff0c;白鲸开源CEO郭炜在2024 DataOps发展大会上被正式聘任为DataOps专家&#xff0c;并获得了荣誉证书。本次大会由中国通信标准化协会主办&#xff0c;中关村科学城管委会提供支持&#xff0c;大数据技术标准推进委员会&#xff08;CCSATC601&#xff09;…

【Andoird开发】android获取蓝牙权限,beacon,android-beacon-library

iBeacon 最先是苹果的技术&#xff0c;使用android-beacon-library包可以在android上开发iBeacon 技术。 iBeacon的发明意义重大。它是一种基于蓝牙低功耗&#xff08;Bluetooth Low Energy, BLE&#xff09;技术的定位系统&#xff0c;通过向周围发送信号来标识其位置。这项技…

202472读书笔记|《首先你要快乐,其次都是其次》——快乐至上,允许一切发生

202472读书笔记|《首先你要快乐&#xff0c;其次都是其次》——快乐至上&#xff0c;允许一切发生 《首先你要快乐&#xff0c;其次都是其次》作者林小仙&#xff0c;挺轻松的小漫画&#xff0c;清新的文字。 生而为人&#xff0c;我很抱歉&#xff0c;大可不必。 生活已经很难…

番外篇 | YOLOv8改进之引入YOLOv9的RepNCSPELAN4模块 | 替换YOLOv8的C2f

前言:Hello大家好,我是小哥谈。YOLOv9,作为YOLO(You Only Look Once)系列的最新成员,代表着实时物体检测技术的又一重要里程碑。自YOLO系列算法诞生以来,它就以其出色的性能和简洁的设计思想赢得了广泛的关注和认可。从最初的YOLOv1到如今的YOLOv9,这个系列不断地进行技…

Linux-文件或目录权限

在使用 ll 时&#xff0c;可以查看文件夹内容的详细信息&#xff0c;信息的第1位表示类型&#xff0c;具体信息如下&#xff1a; 类型说明-普通文件d文件夹b块设备文件c字符设备文件p管道文件s套接口文件 第2-10位表示权限&#xff0c; 举例&#xff1a;rwxr-xr-x 类型说明r…

我在去哪儿薅到了5块钱火车票代金券,速薅

哈哈&#xff0c;亲爱的薅羊毛小伙伴们&#xff01; 刚刚在去哪儿大佬那儿发现了一个超级薅羊毛福利&#xff01;我只花了短短两分钟&#xff0c;就搞到了一张5块钱火车票代金券&#xff0c;简直是天上掉馅饼的节奏啊&#xff01; 话不多说&#xff0c;薅羊毛的姿势给你们摆好…

基于python实现搜索的目标站点内容监测系统

基于python实现搜索的目标站点内容监测系统 开发语言:Python 数据库&#xff1a;MySQL所用到的知识&#xff1a;Django框架工具&#xff1a;pycharm、Navicat、Maven 系统功能实现 登录页面 后台的登录一般是为了管理员的管理方便进行一个用户权限的验证。也是为管理员提供的唯…

成都爱尔胡建斌院长提醒近视超过600度,记得每年检查眼底!

高度近视是指近视度数在600度及以上的一种屈光不正的状态。 近视的眼睛必定是变形的。在正常情况下&#xff0c;人的眼球类似球体&#xff0c;但随着近视加深&#xff0c;眼轴变长&#xff0c;眼球体积逐渐增大&#xff0c;整个眼球从圆球型向椭圆球形发展&#xff0c;而眼球壁…

零门槛微调大模型:基于 Ludwig 低代码框架使用 LoRA 技术微调实践

一、Ludwig 介绍 自然语言处理 (NLP) 和人工智能 (AI) 的飞速发展催生了许多强大的模型&#xff0c;它们能够理解和生成如同人类般的文本&#xff0c;为聊天机器人、文档摘要等应用领域带来了革命性的改变。然而&#xff0c;释放这些模型的全部潜力需要针对特定用例进行微调。…

成都爱尔周进院长提醒当双眼度数差距过大,我们该做些什么

每个人的用眼方式、用眼习惯且两只眼睛“天生条件”不一定相同&#xff0c;当发生近视&#xff0c;双眼近视程度也就可能不同&#xff0c;双眼度数必然会变得不一样。当双眼度数产生差异&#xff0c;尤其是当双眼度数差别过大时会引发哪些问题&#xff1f; 双眼度数不一致&…

37. 解数独 - 力扣(LeetCode)

基础知识要求&#xff1a; Java&#xff1a; 方法、for循环、if else语句、数组 Python&#xff1a; 方法、for循环、if else语句、列表 题目&#xff1a; 编写一个程序&#xff0c;通过填充空格来解决数独问题。 数独的解法需 遵循如下规则&#xff1a; 数字 1-9 在每一行…

vs无法打开或包括文件”QTxxx“

vs创建项目时默认引入core、gui、和widgets等模块&#xff0c;在需要网络通讯或者图表等开发时需要添加相应模块。 点击扩展 -> QT VS Tools -> QT Project Setting->Qt Modules&#xff0c;添加相应模块即可

南加州大学字节提出MagicPose,提供逼真的人类视频生成,实现生动的运动和面部表情传输,以及不需要任何微调的一致的野外零镜头生成。

MagicPose可以精确地生成外观一致的结果&#xff0c;而原始的文本到图像模型(如Stable Diffusion和ControlNet)很难准确地保持主体身份信息。 此外&#xff0c;MagicPose模块可以被视为原始文本到图像模型的扩展/插件&#xff0c;而无需修改其预训练的权重。 相关链接 论文链…

【BSP开发经验】简易文件系统digicapfs实现方式

文章目录 背景Linux vfs框架介绍数据结构系统调用openwriteread 总体框架 Linux 磁盘高速缓存机制标准文件访问同步文件访问异步文件访问buffer_head 如何实现一个简单的文件系统blkdevfs注册文件系统产生一个文件让文件变得可读可写 背景 在新的分区升级启动方案中需要分别实…