《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就不再适用,此时就需要使用分布式锁来保证多服务之间加锁的安全性。 常见的分布式锁的实现方式有ÿ…...
在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能
下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能,包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...
Auto-Coder使用GPT-4o完成:在用TabPFN这个模型构建一个预测未来3天涨跌的分类任务
通过akshare库,获取股票数据,并生成TabPFN这个模型 可以识别、处理的格式,写一个完整的预处理示例,并构建一个预测未来 3 天股价涨跌的分类任务 用TabPFN这个模型构建一个预测未来 3 天股价涨跌的分类任务,进行预测并输…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个生活电费的缴纳和查询小程序
一、项目初始化与配置 1. 创建项目 ohpm init harmony/utility-payment-app 2. 配置权限 // module.json5 {"requestPermissions": [{"name": "ohos.permission.INTERNET"},{"name": "ohos.permission.GET_NETWORK_INFO"…...
【C++从零实现Json-Rpc框架】第六弹 —— 服务端模块划分
一、项目背景回顾 前五弹完成了Json-Rpc协议解析、请求处理、客户端调用等基础模块搭建。 本弹重点聚焦于服务端的模块划分与架构设计,提升代码结构的可维护性与扩展性。 二、服务端模块设计目标 高内聚低耦合:各模块职责清晰,便于独立开发…...
Pinocchio 库详解及其在足式机器人上的应用
Pinocchio 库详解及其在足式机器人上的应用 Pinocchio (Pinocchio is not only a nose) 是一个开源的 C 库,专门用于快速计算机器人模型的正向运动学、逆向运动学、雅可比矩阵、动力学和动力学导数。它主要关注效率和准确性,并提供了一个通用的框架&…...
在QWebEngineView上实现鼠标、触摸等事件捕获的解决方案
这个问题我看其他博主也写了,要么要会员、要么写的乱七八糟。这里我整理一下,把问题说清楚并且给出代码,拿去用就行,照着葫芦画瓢。 问题 在继承QWebEngineView后,重写mousePressEvent或event函数无法捕获鼠标按下事…...
Go语言多线程问题
打印零与奇偶数(leetcode 1116) 方法1:使用互斥锁和条件变量 package mainimport ("fmt""sync" )type ZeroEvenOdd struct {n intzeroMutex sync.MutexevenMutex sync.MutexoddMutex sync.Mutexcurrent int…...
Golang——9、反射和文件操作
反射和文件操作 1、反射1.1、reflect.TypeOf()获取任意值的类型对象1.2、reflect.ValueOf()1.3、结构体反射 2、文件操作2.1、os.Open()打开文件2.2、方式一:使用Read()读取文件2.3、方式二:bufio读取文件2.4、方式三:os.ReadFile读取2.5、写…...
Linux中《基础IO》详细介绍
目录 理解"文件"狭义理解广义理解文件操作的归类认知系统角度文件类别 回顾C文件接口打开文件写文件读文件稍作修改,实现简单cat命令 输出信息到显示器,你有哪些方法stdin & stdout & stderr打开文件的方式 系统⽂件I/O⼀种传递标志位…...
链式法则中 复合函数的推导路径 多变量“信息传递路径”
非常好,我们将之前关于偏导数链式法则中不能“约掉”偏导符号的问题,统一使用 二重复合函数: z f ( u ( x , y ) , v ( x , y ) ) \boxed{z f(u(x,y),\ v(x,y))} zf(u(x,y), v(x,y)) 来全面说明。我们会展示其全微分形式(偏导…...
