气象网站建设/优化设计单元测试卷
《LeetCode力扣练习》代码随想录——字符串(KMP算法学习补充——针对next数组构建的回退步骤进行解释)
学习路径
-
代码随想录:28. 实现 strStr()
-
CSDN:【详解】KMP算法——多图,多例子(c语言)
个人补充
-
看了以上学习路径后,对于KMP有了很深的认识,但是两位作者都没有提到一个重要的步骤的原因——构造next数组时
k=next[k]; // 向前回退
这一步骤的原因和思想。其实这一步我认为是KMP的精髓所在,也是KMP思想的体现,所以在理解之后,将想法记录下来,方便回顾。 -
个人理解KMP的精髓是:不要浪费。已经匹配过的字符串就算遇到不匹配的字符也不要浪费,还有利用的空间,有点像剥削了…
-
CSDN文章中,构造next数组的时候,当遇到不匹配的字符时,需要向前回退的例子还是过于特殊,导致回退一次就可以匹配上,这里我又重新构造了新的字符串:
分别是求next[6]和next[8]的值。
在构建next数组的时候,同时也运用到了KMP算法,并不是在搜寻字符串的时候才运用到,有点递归的感觉
以第二个next为例,当根据之前的最长相等前后缀aba、aba无法直接求得更长的前后缀时(b!=c,否则可以直接构成abac、abac了,直接赋值4),这时候不能直接放弃,还没有榨干之前字符串的价值,我们需要跳转
k=next[k];
重点来了,为什么要跳转到next[k]呢?
aba、aba是两个最长相等前后缀,同时他们自己也有自己的最长相等前后缀。并且第一个aba的最长相等前缀和第二个aba的最长相等后缀(因为两个字符串是相等的)这一点很重要!!!
next[k]
还有一层含义:阻止当前的最大相等前后缀成长为更长的相等前后缀的字符,也就是说这个字符阻止了更长的最大相等字符串的出现!!!当第一个
next[k]
匹配失败后,我们跳到第二个next[k]
,组织第一个aba的最长相等前后缀a变得更长的字符b的位置,因为上面所说的,我要尝试一下第一个aba的前缀+阻止字符和第二个aba的后缀+当前字符next[7]对应的b能否组成一对最长相等前后缀,这样的话(aba、aba这一对就没有被浪费,还可以利用他们本身的前后缀再次查找,并且由于这一对本身没有成功,所以他们的字串如果成功的话必然是最大的相等前后缀)总结一下,这个回退的操作有点像二分法的感觉,第一个前后缀不行,就把他们分开,看前缀的前缀+阻止字符和后缀的后缀+新匹配的字符 能否构成新的前后缀,如果还不行就在回退,再一分为二,一直到第一个字符都不行,next[k]为-1,就代表着一点都不一样,赋值为0,表示没有了。
构建next数组和字符串匹配都用到了KMP,区别是什么呢?next是用前缀的前缀去匹配后缀的后缀;字符串匹配是前缀不行,换前缀的前缀上,不行的话再试。两个操作基本一样,但是next在于写入值,字符串匹配在于移动。
-
到这里我个人的解释就结束了,我是自己把这里想明白之后,KMP算法就顿悟了,没想明白之前,每次回退都十分忐忑。
-
我的具体实现代码在这里:《LeetCode力扣练习》代码随想录——字符串(实现 strStr()—Java)
相关文章:

《LeetCode力扣练习》代码随想录——字符串(KMP算法学习补充——针对next数组构建的回退步骤进行解释)
《LeetCode力扣练习》代码随想录——字符串(KMP算法学习补充——针对next数组构建的回退步骤进行解释) 学习路径 代码随想录:28. 实现 strStr() CSDN:【详解】KMP算法——多图,多例子(c语言) …...

【CANoe】CAPL中on signal和on signal_update的区别
文章目录 CAN信号事件 CAN信号事件 CAN信号事件是在CAN总线上出现指定的信号时被调用(需要配合DBC文件使用)。 关键字为:on signal xxx或on signal_update xxx。 on signal xxx:只在指定信号的值发生变化时被调用, on signal_u…...

ArrayList集合的两个实例应用,有趣的洗牌算法与杨辉三角
本节课的内容,就让我们来学习一下ArrayList集合的应用,ArrayList的本质就是一个顺序表,那下面一起来学习吧 目录 一、杨辉三角 1.题目详情及链接 2.剖析题目 3.思路及代码 二、洗牌算法 1.创造牌对象 2.创造一副牌 3.洗牌操作 4.发…...

Qt 剪贴板操作
Qt剪贴板操作 剪贴板的操作经常和前面所说的拖放技术在一起使用,因此我们现在先来说说剪贴板的相关操作。大家对剪贴板都很熟悉。我们可以简单的把它理解成一个数据的存储池,可以把外面的数据放置进去,也可以把里面的数据取出来。剪贴板是由操作系统维护的,所以这提供了跨…...

python 学习笔记20 批量修改页眉页脚
需求:修改指定目录下所有文件的页眉页脚,或者往里面添加内容。 1. 这里做了word的实现和excel的实现,如下: 需要先安装 pip3 install pywin32,另外页眉页脚格式设置可以参考: word: 浅谈Wor…...

IIS + Axios 跨域设置
1、服务器端设置IIS (web.config) 即可,不需要对django settings.py做配置(python manage.py runserver 才需要settings.py配置跨域,IIS在iis上配) 网站根目录的web.config中加上这段: <httpProtocol&…...

详细说说vuex
Vuex 是什么 Vuex有几个属性及作用注意事项vuex 使用举例Vuex3和Vuex4有哪些区别 创建 Store 的方式在组件中使用 Store辅助函数的用法响应式的改进Vuex4 支持多例模式 Vuex 是什么 Vuex是一个专门为Vue.js应用设计的状态管理构架,它统一管理和维护各个Vue组件的可…...

Qt之Ui样式表不影响子类的配置
Qt之Ui样式表不影响子类的配置 问题 在ui界面上布局时,当对容器进行样试设计时,会对容器内其它成员对象也进行了修改 分析 对应*.ui文件内容 从这个写法来看,它的样式属性会影响其成员对象样式属性。 解决方法 在容器的样式表中写时适…...

Java集合--Map
1、Map集合概述 在Java的集合框架中,Map为双列集合,在Map中的元素是成对以<K,V>键值对的形式存在的,通过键可以找对所对应的值。Map接口有许多的实现类,各自都具有不同的性能和用途。常用的Map接口实现类有HashMap、Hashtab…...

C语言—每日选择题—Day48
第一题 1. 已知宏定义: #define M y*y3*y , 则表达式 s3*M4*My*M 预处理阶段后的结果是 A:s3*(y*y3*y)4*(y*y3*y)y*(y*y3*y) B:s3*(y*y)3*y4*(y*y)3*yy*(y*y)3*y C:s3*y*y3*y4*y*y3*yy*y*y3*y D:s3*(y*y)(3…...

华为OD试题七(IPv4地址转换成整数、比赛的冠亚季军)
1. IPv4地址转换成整数 示例代码: #测试数据 s1 "100#101#1#5"def fun(s):s_list s.split("#")# 转化成十六进制数 左边补零s_16_list [hex(int(_))[2:].zfill(2) for _ in s_list]s_16_str .join(s_16_list)return int(s_16_str,16) r f…...

SVN优缺点详解及版本控制系统选型建议
Subversion (SVN)是目前可用的众多版本控制选项之一。本篇文章将全面概述什么是 SVN、SVN的历史、SVN存储库是什么,以及在切换到SVN之前您应该谨慎考虑的潜在问题。 什么是Subversion(SVN)? Subversion软件,也称为SV…...

自己动手写数据库: select 查询语句对应查询树的构造和执行
首先我们需要给原来代码打个补丁,在SelectScan 结构体初始化时需要传入 UpdateScan 接口对象,但很多时候我们需要传入的是 Scan 对象,因此我们需要做一个转换,也就是当初始化 SelectScan 时,如果传入的是 Scan 对象&am…...

扬声器(喇叭)
扬声器(喇叭) 电子元器件百科 文章目录 扬声器(喇叭)前言一、扬声器(喇叭)是什么二、扬声器(喇叭)的类别三、扬声器(喇叭)的应用场景四、扬声器(喇叭)的作用原理总结前言 扬声器广泛应用于音响系统、公共广播系统、汽车音响、电视、电脑和移动设备等各种电子设备…...

汇总大厂-校招/社招 Java面试题--持续补充更新中-大家别光收藏,要看起来,巩固基础,就是干呀!
** 接上篇-汇总大厂-校招/社招 Java面试题(补充) ** markdown文件。持续更新中(阿里、腾讯、网易、美团、京东、华为、快手、字节…) 上面这篇也结合着看啊,通宵给整理出来的。 如需下载整套资料。关注公众号后台。…...

六. 函数
基本使用 ts与js一样拥有具名函数和匿名函数两种函数类型。但是ts的函数需要提前定义好参数类型以及函数的返回值类型。 具名函数 function add(num1: number, num2: number):number {return num1 num2 }匿名函数 匿名函数的定义相对麻烦,我们需要提前定义函数的…...

SpringBoot的Starter自动化配置,自己编写配置maven依赖且使用及短信发送案例
目录 一、Starter机制 1. 是什么 2. 有什么用 3. 应用场景 二、短信发送案例 1. 创建 2. 配置 3. 编写 4. 形成依赖 6. 其他项目的使用 每篇一获 一、Starter机制 1. 是什么 SpringBoot中的starter是一种非常重要的机制(自动化配置),能够抛弃以前繁杂…...

<蓝桥杯软件赛>零基础备赛20周--第9周--前缀和与差分
报名明年4月蓝桥杯软件赛的同学们,如果你是大一零基础,目前懵懂中,不知该怎么办,可以看看本博客系列:备赛20周合集 20周的完整安排请点击:20周计划 每周发1个博客,共20周(读者可以按…...

LeetCode-2487. 从链表中移除节点【栈 递归 链表 单调栈】
LeetCode-2487. 从链表中移除节点【栈 递归 链表 单调栈】 题目描述:解题思路一:可以将链表转为数组,然后从后往前遍历,遇到大于等于当前元素的就入栈,最终栈里面的元素即是最终的答案。解题思路二:递归&am…...

Redisson分布式锁原理分析
1.Redisson实现分布式锁 在分布式系统中,涉及到多个实例对同一资源加锁的情况,传统的synchronized、ReentrantLock等单进程加锁的API就不再适用,此时就需要使用分布式锁来保证多服务之间加锁的安全性。 常见的分布式锁的实现方式有ÿ…...

【Linux】:线程(二)互斥
互斥与同步 一.线程的局部存储二.线程的分离三.互斥1.一些概念2.上锁3.锁的原理4.死锁 一.线程的局部存储 例子 可以看到全局变量是所有线程共享的,如果我们想要每个线程都单独访问g_val怎么办呢?其实我们可以在它前面加上__thread修饰。 这就相当于把g…...

vscode报错Pylance client: couldn‘t create connection to server.
问题描述: 一打开vscode,右下角就弹报错,Pylance client: couldn’t create connection to server.,让我打开output,打开后似乎是在说连不上server 因为连不上server,所以我的python代码没法解析࿰…...

智能优化算法应用:基于萤火虫算法3D无线传感器网络(WSN)覆盖优化 - 附代码
智能优化算法应用:基于萤火虫算法3D无线传感器网络(WSN)覆盖优化 - 附代码 文章目录 智能优化算法应用:基于萤火虫算法3D无线传感器网络(WSN)覆盖优化 - 附代码1.无线传感网络节点模型2.覆盖数学模型及分析3.萤火虫算法4.实验参数设定5.算法结果6.参考文…...

MacOS多屏状态栏位置不固定,程序坞不小心跑到副屏
目录 方式一:通过系统设置方式二:鼠标切换 MacOS多屏状态栏位置不固定,程序坞不小心跑到副屏 方式一:通过系统设置 先切换到左边 再切换到底部 就能回到主屏了 方式二:鼠标切换 我的两个屏幕放置位置如下 鼠标在…...

Python:pipdeptree 语法介绍
相信大家在按照一些包的时候经常会碰到版本不兼容,但是又不知道版本之间的依赖关系,今天给大家介绍一个工具:pipdeptree pipdeptree 是一个 Python 包,用于查看已安装的 pip 包及其依赖关系。它以树形结构展示包之间的依赖关系&am…...

【问题处理】—— lombok 的 @Data 大小写区分不敏感
问题描述 今天在项目本地编译的时候,发现有个很奇怪的问题,一直提示某位置找不到符号, 但是实际在Idea中显示确实正常的,一开始以为又是IDEA的故障,所以重启了IDEA,并执行了mvn clean然后重新编译。但是问…...

跟着我学Python基础篇:08.集合和字典
往期文章 跟着我学Python基础篇:01.初露端倪 跟着我学Python基础篇:02.数字与字符串编程 跟着我学Python基础篇:03.选择结构 跟着我学Python基础篇:04.循环 跟着我学Python基础篇:05.函数 跟着我学Python基础篇&#…...

Tomcat部署(图片和HTML等)静态资源时遇到的问题
文章目录 Tomcat部署静态资源问题图中HTML代码启动Tomcat后先确认Tomcat是否启动成功 Tomcat部署静态资源问题 今天,有人突然跟我提到,使用nginx部署静态资源,如图片。可以直接通过url地址访问,为什么他的Tomcat不能通过这样的方…...

在接触新的游戏引擎的时候,如何能快速地熟悉并开发出一款新游戏?
引言 大家好,今天分享点个人经验。 有一定编程经验或者游戏开发经验的小伙伴,在接触新的游戏引擎的时候,如何能快速地熟悉并开发出一款新游戏? 利用现成开发框架。 1.什么是开发框架? 开发框架,顾名思…...

计网 - TCP四次挥手原理全曝光:深度解析与实战演示
文章目录 Pre导图过程分析抓包实战第一次挥手 【FIN ACK】第二次挥手 【ACK】第三次挥手 【FINACK】第四次挥手 【ACK】 小结 Pre 计网 - 传输层协议 TCP:TCP 为什么握手是 3 次、挥手是 4 次? 计网 - TCP三次握手原理全曝光:深度解析与实战…...