当前位置: 首页 > news >正文

LeetCode KMP 算法

可以参考

https://www.bilibili.com/video/BV1AY4y157yL/

kmp 主要做的就是子串匹配,类似C程序的 strstr() 函数

记录一下,也防止我自己忘记

传统暴力求解算法是

源串 ssssssssa
子串 sssa(下面暴力求解)
先 (子串从 0 位置匹配,并且匹配到最后一个字符才发现不对,白搞)
ssssssssasssa其次 (子串从 0 位置匹配,并且匹配到最后一个字符才发现不对,白搞)
ssssssssasssa再后面就是 (子串从 0 位置匹配,并且匹配到最后一个字符才发现不对,白搞)
ssssssssasssa

效率不高

kmp的算法出现,就是为了解决这个问题

kmp是由三位大佬发现的,他们三人的名字首字母分别就是K、M、P

有没有一种办法就是少做无用功,在刚刚那个场景下

先 (a和c不匹配)
ssssssssa
sssa其次,(子串从 2 位置匹配)
ssssssssasssa然后,(子串从 2 位置匹配)
ssssssssasssa.......最后
然后,(子串从 2 位置匹配),匹配成功
ssssssssasssa

从 2 位置匹配,显然提高了匹配速度

但是 2 位置是怎么知道的呢,kmp 算法中就是先计算一个数组叫做 next,这个next计算只需要子串,然后next的作用是记录子串回溯的位置,当源串和子串不匹配时,不像上面那样老是回溯0

子串      sssa
next数组  0120

回溯的位置就是最长前缀的位置

比如

子串      abcabcd
next数组  ...1230
解释
1 是因为 a=a
2 是因为前面已经有匹配字符 a=a 了,那么 现在刚好 b=b,就最长前缀就等于 1 的基础上加 1 等于 2
3 是因为前面已经有匹配字符 a=a b=b 了,那么 现在刚好 c=c,就最长前缀就等于 2 的基础上加 1 等于 3
0 是因为d没有最长前缀为啥next是基于前缀,因为比如我都匹配到最后一位d和a(源串第七个)不相等了,由于前面有相似的前缀
源串 abcabcaeee
子串 abcabcd那么下一步就是 【子串a(第四个)和a(源串第七个,第七个刚刚没匹配上)比,就是因为前缀一样,才敢让子串匹配位置不从0开始,因为前面有相似的结构】
源串 abcabcaeee
子串    abcabcd特殊场景
子串      sssa
next数组  0120
解释
0 是因为s没有最长前缀
1 是因为 第二个s=第一个s
2 是因为前面已经有匹配字符 s=s 了,那么 现在刚好 第三个s=第二个s,就最长前缀就等于 1 的基础上加 1 等于 2

下面需要结合底部计算next函数一起看

子串      sssa
next数组  0120(其实就是在计算前缀)
计算next数组也是有两个下标计算,建议对照下面代码看 (i为遍历字符串的变量,j为最长前缀的下标)
首先 next[0] 肯定是等于0的,第一个就不匹配,那肯定回溯还是0,
那么 next[1] 由于 str[i] == str[j] 即 str[0] == str[1],s==s,前缀相同,j自然++
next[1]=j,即 next[1]=1
由于本题是 sssa
所以会出现子串      sssa
next数组  012?(题外话,我们知道a是在前面没有最长前缀的,最后结果肯定为0)
匹配到最后一位时,我们发现跟前面不相等,j就看看前面有没有相等的,j=2,但是 str[2] 也不等于 a
然后while循环一直往前找最长前缀(从2到1到0),最终没找到,为0但是,比如子串      aaaab....aaaaa
next数组  01230....0123?(此时j为3,i为n)?处 a和b不匹配,j=next[j-1],即 j=next[3-1],即 j=2,而str[2]==str[n],j++,退出
next[n]=3,这里j没有从0开始,快了一点,其实从0开始也能算出3这个结果最终结果为
子串      aaaab....aaaaa
next数组  01230....01233

上代码

class Solution {
public:int strStr(string haystack, string needle) {// 计算nextvector<int> next(needle.length(), 0);getNext(needle, next);// 匹配过程int j=0;int i=0;for(;i<haystack.length() && j<needle.length();) {// 当前串匹配if (haystack[i]==needle[j]) {j++;i++;} else  {// 当前串不匹配if (j==0)// 防止j一直卡在0,死循环i++;else// 当前串不匹配,但是i的值不自增,只改变j j=next[j-1];}}// 返回结果if (j==needle.length())return i-j;elsereturn -1;}void getNext(string &str,vector<int> &next) {// j 从 0 开始, i 从 1 开始,已知第一个 next[0] 一定是等于 0 的,因为前面没有字符了for(int j=0,i=1;i<str.length();i++) {// 当前如果不匹配,那就去看看它前一个的下标位置对应的字符是否匹配while (j > 0 && str[i] != str[j]) {j=next[j-1];}// 当前如果匹配,j 往前走if(str[i]==str[j]) {j++;}// j 走多远,前缀最长就是多远next[i] = j;}}
};

相关文章:

LeetCode KMP 算法

可以参考https://www.bilibili.com/video/BV1AY4y157yL/kmp 主要做的就是子串匹配&#xff0c;类似C程序的 strstr() 函数记录一下&#xff0c;也防止我自己忘记传统暴力求解算法是源串 ssssssssa 子串 sssa&#xff08;下面暴力求解&#xff09; 先 (子串从 0 位置匹配&#x…...

全面剖析OpenAI发布的GPT-4比其他GPT模型强在哪里

最强的文本生成模型GPT-4一、什么是GPT-4二、GPT-4的能力三、和其他GPT模型比较3.1、增加了图像模态的输入3.2、可操纵性更强3.3、复杂任务处理能力大幅提升3.4、幻觉、安全等局限性的改善3.6、风险和缓解措施改善更多安全特性3.7、可预测的扩展四、与之前 GPT 系列模型比较五、…...

leetcode——26. 删除有序数组中的重复项

文章目录&#x1f428;1. 题目&#x1f3f9;2. 思路&#x1fa83;3. 代码实现&#x1f428;1. 题目 给你一个升序排列的数组nums&#xff0c;请你原地删除重复出现的元素&#xff0c;使每个元素只出现一次&#xff0c;返回删除后数组的新长度。元素的相对顺序应该保持一致。 由…...

基于springboot垃圾分类网站设计实现【毕业论文、源码】

摘要本论文主要论述了如何使用JAVA语言开发一个垃圾分类网站&#xff0c;本系统将严格按照软件开发流程进行各个阶段的工作&#xff0c;采用B/S架构&#xff0c;面向对象编程思想进行项目开发。在引言中&#xff0c;作者将论述垃圾分类网站的当前背景以及系统开发的目的&#x…...

计算机组成原理实验一(完整)

在VC中使用调试功能将下列语句运行的内存存放结果截图&#xff0c;每运行一句需截图一次。 #include<stdio.h> int main() {int a 你的学号末两位-100; //0x&#xff1f;&#xff1f;&#xff1f;&#xff1f;&#xff1f;&#xff1f;&#xff1f;&#xff1f;&#x…...

【SSM】MyBatis(一.基础)

文章目录1.ORM2. 数据库表3. 入门程序3.1 创建项目3.2 开发3.3 一个比较完整规格的mybatis程序3.4 测试案例 junit3.5 对第一个mybatis使用junit测试3.6 集成日志框架logback3.7mybatis工具类编写1.ORM Object(JVM中的Java对象) Relational(关系型数据库) Mapping(映射) mybat…...

LInux指令之文件目录类

文章目录一、帮助指令二、文件目录类ls指令cd指令 &#xff08;切换目录&#xff09;mkdir指令&#xff08;创建目录&#xff09;rmdir指令&#xff08;删除目录&#xff09;touch指令&#xff08;创建空文件&#xff09;cp指令(拷贝文件)rm指令mv指令cat指令(查看)more指令les…...

【c++】:STL中vector的模拟使用及模拟实现

文章目录 前言一.使用库中vector常用接口二.vector的模拟实现总结前言 上一篇我们讲解了STL中的string的使用和模拟实现&#xff0c;这次我们就来讲解STL中的vector&#xff0c;vector相对于string来说模拟实现会难一些&#xff0c;难点在于迭代器失效问题和深浅拷贝问题。 首…...

C++ STL:vector的使用方法及模拟实现

目录 一. vector概述 二. vector接口函数的使用方法和模拟实现 2.1 vector类模板的成员变量 2.2 构造函数的使用和模拟实现 2.2.1 构造函数的使用方法 2.2.2 构造函数的模拟实现 2.3 析构函数的模拟实现 2.4 赋值运算符重载函数的使用和模拟实现 2.4.1 函数的使用 2.…...

naive UI 的upload组件自定义手动上传图片的base64位

<template><n-upload ref"uploadRef" action"#" :default-upload"false" :custom-request"myUpload"><n-button>点击选择文件</n-button></n-upload><n-button click"submitUpload"> 上…...

信创办公–基于WPS的PPT最佳实践系列(表格和图标常用动画)

信创办公–基于WPS的PPT最佳实践系列&#xff08;表格和图标常用动画&#xff09; 目录应用背景操作步骤图表常用动画效果&#xff1a;擦除效果表格常用动画效果&#xff1a;轮子效果应用背景 文不如表&#xff0c;表不如图。在平时用ppt做总结时&#xff0c;我们会经常用到图…...

Spring Bean实例化和初始化的过程

承接上文Spring Bean生命周期应用程序在运行过程中能否去读取当前系统的环境变量或系统属性?这里涉及到一个非常重要的接口Environment&#xff0c;System.getenv&#xff0c;System.getProperties都是获取当前系统环境变量&#xff0c;Environment接口的实现类AbstractEnviro…...

WorkTool企微机器人接入智能问答

一、前言 最新版的企微机器人已经集成 Chat &#xff0c;无需开发可快速搭建智能对话机器人。 从官方介绍看目前集成版本使用模型为 3.5-turbo。 二、入门 创建 WorkTool 机器人 你可以通过这篇快速入门教程&#xff0c;来快速配置一个自己的企微机器人。 实现的流程如图&…...

C导入正则库问题

环境 操作系统:win11 专业版 gcc: gcc (x86_64-posix-seh-rev0, Built by MinGW-W64 project) 8.1.0 编辑器&#xff1a;vscode 要求 在c中使用正则表达式 遇到的问题以及解决思路 C标准中并没有正则表达式库 从其他地方下载正则表达式库即可。 http://gnuwin32.sourcefo…...

尚融宝05-Node.js入门

目录 一、Node.js的概念 1、JavaScript引擎 2、什么是Node.js 二、下载和安装 1、下载和安装 2、查看安装是否成功 三、初始Node.js程序 1、运行一个程序 常见问题 2、文件的读取 3、服务器端程序 三、Node.js的作用 1、Node.js的应用场景 2、BFF 解决什么问题 …...

「SAP ABAP」OPEN SQL(八)【WHERE语句大全】

&#x1f482;作者简介&#xff1a; THUNDER王&#xff0c;一名热爱财税和SAP ABAP编程以及热爱分享的博主。目前于江西师范大学本科在读&#xff0c;同时任汉硕云&#xff08;广东&#xff09;科技有限公司ABAP开发顾问。在学习工作中&#xff0c;我通常使用偏后端的开发语言A…...

Ribbon负载均衡的原理(源码分析)

SpringCloud底层其实是利用了一个名为Ribbon的组件&#xff0c;来实现负载均衡功能的。1&#xff09;LoadBalancerIntercepor可以看到这里的intercept方法&#xff0c;拦截了用户的HttpRequest请求&#xff0c;然后做了几件事&#xff1a;1.request.getURI()&#xff1a;获取请…...

用sql计算两个经纬度坐标距离(米数互转)

目录 一、sql示例&#xff08;由近到远&#xff09; 二 、参数讲解 三、查询效果 - 距离&#xff08;公里 / 千米&#xff09; 四、查询效果 - 距离&#xff08;米&#xff09; 五、距离四舍五入保留后2位小数&#xff08;java&#xff09; 一、sql示例&#xff08;由近到远…...

C语言详解KMP算法

如果给你一个字符串 和 该字符串的一个子字符串 你能否快速找出该子字符串的所在位置我猜 这里会有一群杠精 说可以找到 真的吗 那下面这个字符串你可以一眼看出来吗你能找出来吗 如果能 算你眼神好 如果不能 那就看看接下来我怎么做你有想到暴力求解法吗&#xff1f;——来自百…...

redis在window上安装与自启动

需求&#xff1a; 客户window服务器使用redis&#xff0c;需要配置成在window服务中&#xff0c;并且可以随着电脑自启动服务。 下载 https://github.com/tporadowski/redis/releases打开上面的下载地址&#xff0c;这里我们下载zip压缩版本。 解压到待安装目录下&#xff…...

KubeSphere 容器平台高可用:环境搭建与可视化操作指南

Linux_k8s篇 欢迎来到Linux的世界&#xff0c;看笔记好好学多敲多打&#xff0c;每个人都是大神&#xff01; 题目&#xff1a;KubeSphere 容器平台高可用&#xff1a;环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...

脑机新手指南(八):OpenBCI_GUI:从环境搭建到数据可视化(下)

一、数据处理与分析实战 &#xff08;一&#xff09;实时滤波与参数调整 基础滤波操作 60Hz 工频滤波&#xff1a;勾选界面右侧 “60Hz” 复选框&#xff0c;可有效抑制电网干扰&#xff08;适用于北美地区&#xff0c;欧洲用户可调整为 50Hz&#xff09;。 平滑处理&…...

Appium+python自动化(十六)- ADB命令

简介 Android 调试桥(adb)是多种用途的工具&#xff0c;该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具&#xff0c;其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利&#xff0c;如安装和调试…...

遍历 Map 类型集合的方法汇总

1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...

学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1

每日一言 生活的美好&#xff0c;总是藏在那些你咬牙坚持的日子里。 硬件&#xff1a;OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写&#xff0c;"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...

视频字幕质量评估的大规模细粒度基准

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用&#xff0c;因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型&#xff08;VLMs&#xff09;在字幕生成方面…...

【AI学习】三、AI算法中的向量

在人工智能&#xff08;AI&#xff09;算法中&#xff0c;向量&#xff08;Vector&#xff09;是一种将现实世界中的数据&#xff08;如图像、文本、音频等&#xff09;转化为计算机可处理的数值型特征表示的工具。它是连接人类认知&#xff08;如语义、视觉特征&#xff09;与…...

Psychopy音频的使用

Psychopy音频的使用 本文主要解决以下问题&#xff1a; 指定音频引擎与设备&#xff1b;播放音频文件 本文所使用的环境&#xff1a; Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...

C#中的CLR属性、依赖属性与附加属性

CLR属性的主要特征 封装性&#xff1a; 隐藏字段的实现细节 提供对字段的受控访问 访问控制&#xff1a; 可单独设置get/set访问器的可见性 可创建只读或只写属性 计算属性&#xff1a; 可以在getter中执行计算逻辑 不需要直接对应一个字段 验证逻辑&#xff1a; 可以…...

纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join

纯 Java 项目&#xff08;非 SpringBoot&#xff09;集成 Mybatis-Plus 和 Mybatis-Plus-Join 1、依赖1.1、依赖版本1.2、pom.xml 2、代码2.1、SqlSession 构造器2.2、MybatisPlus代码生成器2.3、获取 config.yml 配置2.3.1、config.yml2.3.2、项目配置类 2.4、ftl 模板2.4.1、…...