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

KMP算法详解

1. 问题引入

链接:leetcode_28

题目:s1字符串是否包含s2字符串,如果包含返回s1中包含s2的最左开头位置,不包含返回-1

暴力方法就是s1的每个位置都做开头,然后去匹配s2整体,时间复杂度O(n*m)

KMP算法可以做到时间复杂度O(n+m),那这个算法是怎样实现的呢?

2. 核心概念:最长公共前后缀

对于某个字符,不含该字符,前面的字符串的前后缀最大匹配长度,需要把这些数值传给一个数组(next数组),下标 i 表示第 i 个字符前的字符串(即从 0 ~ i-1 的字符串)的前后缀最大匹配长度

非常不好理解,请看示例:

这个玩意有什么用呢,看后面的核心步骤就理解了。

3. 核心过程

 【过程分解】

在比对的过程中,有两个数 xy 记录两者对比到的下标

1)当两字符相同,同时x++y++,继续对比下一个数据就好了

2)当s1s2对应的字符不匹配时,则将y跳转到next数组对应数据下标的字符,在此例子中是将y跳转到下标6的位置

PS:每次跳转时,如果此时y0,只需要x++即可,因为y已经没有可以再退的字符了


跳转之后:

此时xy对应的下标依旧不匹配,再按照之前的逻辑,找此时y对应的next数组的数据,并跳转,应该跳转到3


再跳转后:

xy对应的字符相同时,在x++y++看下一个字符是否匹配,但是因为x已经越界,但s2还没匹配完,说明匹配失败,返回 -1

【总结】

一共有两种情况分别是

  1. 两字符相同,同时x++y++,看后续是否相同
  2. 两字符不同,但y在下标0位置,只需要x++;若y不在0位置,将y定位到对应next数组相应数据的位置

在每一次操作结束时,都需要判断xy是否已经越界

如果y等于s2的长度(包括x和y同时越界和只有y越界),则说明匹配成功,结果为x-y (情况1

否则,x越界,y没越界,说明匹配失败,返回-1     (情况2

此处对应代码的return返回值

【解惑】

1)为什么s20~5下标的字符和s17~12下标的字符对应,可以直接不用比对?

2)如果在s1的7下标之前还有与s2配对吗?

没有了,因为next数组就已经决定了这是最长的前后缀匹配长度,再长就不匹配了

  • 为什么会加速?

每次匹配时只需要从该字符对应的 next 数组的数开始匹配,相当于跳过了一部分的数据对比过程

【next 数组的创建】

有点类似动态规划,通过前面的已知数据,推出当前的数据

操作过程

前一位的字符,与其next数组对应的下标的字符相同,则该字符对应的数为此下标数+1

如果不相同,若 next 数组对应数据不为0,则跳转到对应下标,若为0则此字符对应 next 值为0

4. 例题

如果还不是很清晰,可以结合模版题和代码一起分析,会更好理解

模版题:链接

参考代码:

class Solution {
public:int strStr(string s1, string s2) {int m = s1.size(), n = s2.size();vector<int> next(n + 5);next[0] = -1;next[1] = 0; // 0和1下标next值默认确定int i = 2, cn = 0; // i表示当前对应下标,cn表示next值// 生成next数组// 结合前面的分析进行情况分类while (i < n){if (s2[i - 1] == s2[cn])next[i++] = ++cn;else if (cn > 0)cn = next[cn];elsenext[i++] = 0;}  int x = 0, y = 0;// x表示s1当前比对的位置// y表示s2当前比对的位置while (x < m && y < n){if (s1[x] == s2[y]){x++;y++;}else if (y == 0)x++;elsey = next[y]; }return y == n ? x - y : -1;}};

相关文章:

KMP算法详解

1. 问题引入 链接&#xff1a;leetcode_28 题目&#xff1a;s1字符串是否包含s2字符串&#xff0c;如果包含返回s1中包含s2的最左开头位置&#xff0c;不包含返回-1 暴力方法就是s1的每个位置都做开头&#xff0c;然后去匹配s2整体&#xff0c;时间复杂度O(n*m) KMP算法可以…...

ubuntu22.04@laptop OpenCV Get Started: 013_contour_detection

ubuntu22.04laptop OpenCV Get Started: 013_contour_detection 1. 源由2. 应用Demo2.1 C应用Demo2.2 Python应用Demo 3. contour_approx应用3.1 读取图像并将其转换为灰度格式3.2 应用二进制阈值过滤算法3.3 查找对象轮廓3.4 绘制对象轮廓3.5 效果3.6 CHAIN_APPROX_SIMPLE v.s…...

[ai笔记5] 个人AI资讯助手实战

欢迎来到文思源想的ai空间&#xff0c;这是技术老兵重学ai以及成长思考的第5篇分享&#xff0c;也是把ai场景化应用的第一篇实操内容&#xff01; 既然要充分学习和了解ai&#xff0c;自然少不了要时常看看ai相关资讯&#xff0c;所以今天特地用字节的“扣子”做了一个ai的资讯…...

QT+OSG/osgEarth编译之八十九:osgdb_ply+Qt编译(一套代码、一套框架,跨平台编译,版本:OSG-3.6.5插件库osgdb_ply)

文章目录 一、osgdb_ply介绍二、文件分析三、pro文件四、编译实践一、osgdb_ply介绍 斯坦福三角形格式(Stanford Triangle Format)是一种用于存储三维模型数据的文件格式,也称为 PLY 格式。它最初由斯坦福大学图形实验室开发,用于存储和共享三维扫描和计算机图形数据。 P…...

机器人专题:我国机器人产业园区发展现状、问题、经验及建议

今天分享的是机器人系列深度研究报告&#xff1a;《机器人专题&#xff1a;我国机器人产业园区发展现状、问题、经验及建议》。 &#xff08;报告出品方&#xff1a;赛迪研究院&#xff09; 报告共计&#xff1a;26页 机器人作为推动工业化发展和数字中国建设的重要工具&…...

算法沉淀——哈希算法(leetcode真题剖析)

算法沉淀——哈希算法 01.两数之和02.判定是否互为字符重排03.存在重复元素04.存在重复元素 II05.字母异位词分组 哈希算法&#xff08;Hash Algorithm&#xff09;是一种将任意长度的输入&#xff08;也称为消息&#xff09;映射为固定长度的输出的算法。这个输出通常称为哈希…...

深入理解Redis哨兵原理

哨兵模式介绍 在深入理解Redis主从架构中Redis 的主从架构中&#xff0c;由于主从模式是读写分离的&#xff0c;如果主节点&#xff08;master&#xff09;挂了&#xff0c;那么将没有主节点来服务客户端的写操作请求&#xff0c;也没有主节点给从节点&#xff08;slave&#…...

MySQL-存储过程(PROCEDURE)

文章目录 1. 什么是存储过程&#xff1f;2. 存储过程的优点3. MySQL中的变量3.1 系统变量3.2 用户自定义变量3.3 局部变量 4. 存储过程的相关语法4.1 创建存储过程&#xff08;CREATE&#xff09;4.2 查看存储过程&#xff08;SHOW&#xff09;4.3 修改存储过程&#xff08;ALT…...

linux系统监控工具prometheus的安装以及监控mysql

prometheus 安装服务端客户端监控mysql prometheus浏览器查看 安装 https://prometheus.io/download/下载客户端和服务端以及需要监控的所有的包服务端 官网下载下载prometheustar -xf prometheus-2.47.2.linux-amd64.tar.gz -C /usr/local/ cd /usr/local/ mv prometheus-2.…...

初识tensorflow程序设计模式

文章目录 建立计算图tensorflow placeholdertensorflow数值运算常用的方法 tensorboard启动tensorboard的方法 建立一维与二维张量建立一维张量建立二维张量建立新的二维张量 矩阵的基本运算矩阵的加法矩阵乘法与加法 github地址https://github.com/fz861062923/TensorFlow 建…...

【QT+QGIS跨平台编译】之三十八:【GDAL+Qt跨平台编译】(一套代码、一套框架,跨平台编译)

文章目录 一、gdal介绍二、文件下载三、文件分析四、pro文件五、编译实践一、gdal介绍 GDAL(Geospatial Data Abstraction Library)是一个用于读取、写入和处理地理空间数据的开源库。它支持多种栅格和矢量地理空间数据格式,包括常见的GeoTIFF、Shapefile、NetCDF、HDF5等,…...

黑马鸿蒙教程学习1:Helloworld

今年打算粗略学习下鸿蒙开发&#xff0c;当作兴趣爱好&#xff0c;通过下华为那个鸿蒙开发认证&#xff0c; 发现黑马的课程不错&#xff0c;有视频和完整的代码和课件下载&#xff0c;装个devstudio就行了&#xff0c;建议32G内存。 今年的确是鸿蒙大爆发的一年呀&#xff0c;…...

蓝桥杯每日一题------背包问题(四)

前言 前面讲的都是背包的基础问题&#xff0c;这一节我们进行背包问题的实战&#xff0c;题目来源于一位朋友的询问&#xff0c;其实在这之前很少有题目是我自己独立做的&#xff0c;我一般习惯于先看题解&#xff0c;验证了题解提供的代码是正确的后&#xff0c;再去研究题解…...

OpenAI发布Sora技术报告深度解读!真的太强了!

&#x1f60e; 作者介绍&#xff1a;我是程序员洲洲&#xff0c;一个热爱写作的非著名程序员。CSDN全栈优质领域创作者、华为云博客社区云享专家、阿里云博客社区专家博主、前后端开发、人工智能研究生。公粽号&#xff1a;洲与AI。 &#x1f388; 本文专栏&#xff1a;本文收录…...

AJAX——接口文档

1 接口文档 接口文档&#xff1a;描述接口的文章 接口&#xff1a;使用AJAX和服务器通讯时&#xff0c;使用的URL&#xff0c;请求方法&#xff0c;以及参数 传送门&#xff1a;AJAX阶段接口文档 <!DOCTYPE html> <html lang"en"><head><meta c…...

leetcode hot100不同路径

本题可以采用动态规划来解决。还是按照五部曲来做 确定dp数组&#xff1a;dp[i][j]表示走到&#xff08;i&#xff0c;j&#xff09;有多少种路径 确定递推公式&#xff1a;我们这里&#xff0c;只有两个移动方向&#xff0c;比如说我移动到&#xff08;i&#xff0c;j&#x…...

【前端工程化面试题目】webpack 的热更新原理

可以在顺便学习一下 vite 的热更新原理&#xff0c;请参考这篇文章。 首先有几个知识点需要明确 热更新是针对开发过程中的开发服务器的&#xff0c;也就是 webpack-dev-serverwebpack 的热更新不需要额外的插件&#xff0c;但是需要在配置文件中 devServer属性中配置&#x…...

不花一分钱,在 Mac 上跑 Windows(M1/M2 版)

这是在 MacOS M1 上体验最新 Windows11 的效果&#xff1a; VMware Fusion&#xff0c;可以运行 Windows、Linux 系统&#xff0c;个人使用 licence 免费 安装流程见 &#x1f449; https://zhuanlan.zhihu.com/p/452412091 从申请 Fusion licence 到下载镜像&#xff0c;再到…...

Attempt to call an undefined function glutInit

Attempt to call an undefined function glutInit 解决方法&#xff1a; 从这里下载PyOpenGL 的whl安装文件&#xff0c; https://drive.google.com/drive/folders/1mz7faVsrp0e6IKCQh8MyZh-BcCqEGPwx 安装命令举栗 pip install PyOpenGL-3.1.7-cp39-cp39-win_amd64.whl pi…...

AB测试最小样本量

1.AB实验过程 常见的AB实验过程&#xff0c;分流-->实验-->数据分析-->决策&#xff1a;分流&#xff1a;用户被随机均匀的分为不同的组实验&#xff1a;同一组内的用户在实验期间使用相同的策略&#xff0c;不同组的用户使用相同或不同的策略。数据收集&#xff1a;…...

零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?

一、核心优势&#xff1a;专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发&#xff0c;是一款收费低廉但功能全面的Windows NAS工具&#xff0c;主打“无学习成本部署” 。与其他NAS软件相比&#xff0c;其优势在于&#xff1a; 无需硬件改造&#xff1a;将任意W…...

多模态2025:技术路线“神仙打架”,视频生成冲上云霄

文&#xff5c;魏琳华 编&#xff5c;王一粟 一场大会&#xff0c;聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中&#xff0c;汇集了学界、创业公司和大厂等三方的热门选手&#xff0c;关于多模态的集中讨论达到了前所未有的热度。其中&#xff0c;…...

Linux 文件类型,目录与路径,文件与目录管理

文件类型 后面的字符表示文件类型标志 普通文件&#xff1a;-&#xff08;纯文本文件&#xff0c;二进制文件&#xff0c;数据格式文件&#xff09; 如文本文件、图片、程序文件等。 目录文件&#xff1a;d&#xff08;directory&#xff09; 用来存放其他文件或子目录。 设备…...

springboot 百货中心供应链管理系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;百货中心供应链管理系统被用户普遍使用&#xff0c;为方…...

使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装

以下是基于 vant-ui&#xff08;适配 Vue2 版本 &#xff09;实现截图中照片上传预览、删除功能&#xff0c;并封装成可复用组件的完整代码&#xff0c;包含样式和逻辑实现&#xff0c;可直接在 Vue2 项目中使用&#xff1a; 1. 封装的图片上传组件 ImageUploader.vue <te…...

【Go】3、Go语言进阶与依赖管理

前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课&#xff0c;做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程&#xff0c;它的核心机制是 Goroutine 协程、Channel 通道&#xff0c;并基于CSP&#xff08;Communicating Sequential Processes&#xff0…...

基于Docker Compose部署Java微服务项目

一. 创建根项目 根项目&#xff08;父项目&#xff09;主要用于依赖管理 一些需要注意的点&#xff1a; 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件&#xff0c;否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...

多种风格导航菜单 HTML 实现(附源码)

下面我将为您展示 6 种不同风格的导航菜单实现&#xff0c;每种都包含完整 HTML、CSS 和 JavaScript 代码。 1. 简约水平导航栏 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport&qu…...

算法笔记2

1.字符串拼接最好用StringBuilder&#xff0c;不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...

推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材)

推荐 github 项目:GeminiImageApp(图片生成方向&#xff0c;可以做一定的素材) 这个项目能干嘛? 使用 gemini 2.0 的 api 和 google 其他的 api 来做衍生处理 简化和优化了文生图和图生图的行为(我的最主要) 并且有一些目标检测和切割(我用不到) 视频和 imagefx 因为没 a…...