《LeetCode力扣练习》代码随想录——字符串(KMP算法学习补充——针对next数组构建的回退步骤进行解释)
《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就不再适用,此时就需要使用分布式锁来保证多服务之间加锁的安全性。 常见的分布式锁的实现方式有ÿ…...
大模型多显卡多服务器并行计算方法与实践指南
一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...
让AI看见世界:MCP协议与服务器的工作原理
让AI看见世界:MCP协议与服务器的工作原理 MCP(Model Context Protocol)是一种创新的通信协议,旨在让大型语言模型能够安全、高效地与外部资源进行交互。在AI技术快速发展的今天,MCP正成为连接AI与现实世界的重要桥梁。…...
网络编程(UDP编程)
思维导图 UDP基础编程(单播) 1.流程图 服务器:短信的接收方 创建套接字 (socket)-----------------------------------------》有手机指定网络信息-----------------------------------------------》有号码绑定套接字 (bind)--------------…...
docker 部署发现spring.profiles.active 问题
报错: org.springframework.boot.context.config.InvalidConfigDataPropertyException: Property spring.profiles.active imported from location class path resource [application-test.yml] is invalid in a profile specific resource [origin: class path re…...
关键领域软件测试的突围之路:如何破解安全与效率的平衡难题
在数字化浪潮席卷全球的今天,软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件,这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下,实现高效测试与快速迭代?这一命题正考验着…...
LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf
FTP 客服管理系统 实现kefu123登录,不允许匿名访问,kefu只能访问/data/kefu目录,不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...
Mysql8 忘记密码重置,以及问题解决
1.使用免密登录 找到配置MySQL文件,我的文件路径是/etc/mysql/my.cnf,有的人的是/etc/mysql/mysql.cnf 在里最后加入 skip-grant-tables重启MySQL服务 service mysql restartShutting down MySQL… SUCCESS! Starting MySQL… SUCCESS! 重启成功 2.登…...
mac 安装homebrew (nvm 及git)
mac 安装nvm 及git 万恶之源 mac 安装这些东西离不开Xcode。及homebrew 一、先说安装git步骤 通用: 方法一:使用 Homebrew 安装 Git(推荐) 步骤如下:打开终端(Terminal.app) 1.安装 Homebrew…...
TSN交换机正在重构工业网络,PROFINET和EtherCAT会被取代吗?
在工业自动化持续演进的今天,通信网络的角色正变得愈发关键。 2025年6月6日,为期三天的华南国际工业博览会在深圳国际会展中心(宝安)圆满落幕。作为国内工业通信领域的技术型企业,光路科技(Fiberroad&…...
小木的算法日记-多叉树的递归/层序遍历
🌲 从二叉树到森林:一文彻底搞懂多叉树遍历的艺术 🚀 引言 你好,未来的算法大神! 在数据结构的世界里,“树”无疑是最核心、最迷人的概念之一。我们中的大多数人都是从 二叉树 开始入门的,它…...
