当前位置: 首页 > 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;…...

el-switch文字内置

el-switch文字内置 效果 vue <div style"color:#ffffff;font-size:14px;float:left;margin-bottom:5px;margin-right:5px;">自动加载</div> <el-switch v-model"value" active-color"#3E99FB" inactive-color"#DCDFE6"…...

力扣-35.搜索插入位置

题目描述 给定一个排序数组和一个目标值&#xff0c;在数组中找到目标值&#xff0c;并返回其索引。如果目标值不存在于数组中&#xff0c;返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...

智能AI电话机器人系统的识别能力现状与发展水平

一、引言 随着人工智能技术的飞速发展&#xff0c;AI电话机器人系统已经从简单的自动应答工具演变为具备复杂交互能力的智能助手。这类系统结合了语音识别、自然语言处理、情感计算和机器学习等多项前沿技术&#xff0c;在客户服务、营销推广、信息查询等领域发挥着越来越重要…...

mac 安装homebrew (nvm 及git)

mac 安装nvm 及git 万恶之源 mac 安装这些东西离不开Xcode。及homebrew 一、先说安装git步骤 通用&#xff1a; 方法一&#xff1a;使用 Homebrew 安装 Git&#xff08;推荐&#xff09; 步骤如下&#xff1a;打开终端&#xff08;Terminal.app&#xff09; 1.安装 Homebrew…...

在 Visual Studio Code 中使用驭码 CodeRider 提升开发效率:以冒泡排序为例

目录 前言1 插件安装与配置1.1 安装驭码 CodeRider1.2 初始配置建议 2 示例代码&#xff1a;冒泡排序3 驭码 CodeRider 功能详解3.1 功能概览3.2 代码解释功能3.3 自动注释生成3.4 逻辑修改功能3.5 单元测试自动生成3.6 代码优化建议 4 驭码的实际应用建议5 常见问题与解决建议…...

快速排序算法改进:随机快排-荷兰国旗划分详解

随机快速排序-荷兰国旗划分算法详解 一、基础知识回顾1.1 快速排序简介1.2 荷兰国旗问题 二、随机快排 - 荷兰国旗划分原理2.1 随机化枢轴选择2.2 荷兰国旗划分过程2.3 结合随机快排与荷兰国旗划分 三、代码实现3.1 Python实现3.2 Java实现3.3 C实现 四、性能分析4.1 时间复杂度…...

C#最佳实践:为何优先使用as或is而非强制转换

C#最佳实践&#xff1a;为何优先使用as或is而非强制转换 在 C# 的编程世界里&#xff0c;类型转换是我们经常会遇到的操作。就像在现实生活中&#xff0c;我们可能需要把不同形状的物品重新整理归类一样&#xff0c;在代码里&#xff0c;我们也常常需要将一个数据类型转换为另…...

2025 后端自学UNIAPP【项目实战:旅游项目】7、景点详情页面【完结】

1、获取景点详情的请求【my_api.js】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口&#xff08;适配服务端返回 Token&#xff09; export const login async (code, avatar) > {const res await http(/login/getWXSessionKey, {code,avatar}); };//…...

break 语句和 continue 语句

break语句和continue语句都具有跳转作用&#xff0c;可以让代码不按既有的顺序执行 break break语句用于跳出代码块或循环 1 2 3 4 5 6 for (var i 0; i < 5; i) { if (i 3){ break; } console.log(i); } continue continue语句用于立即终…...

使用 uv 工具快速部署并管理 vLLM 推理环境

uv&#xff1a;现代 Python 项目管理的高效助手 uv&#xff1a;Rust 驱动的 Python 包管理新时代 在部署大语言模型&#xff08;LLM&#xff09;推理服务时&#xff0c;vLLM 是一个备受关注的方案&#xff0c;具备高吞吐、低延迟和对 OpenAI API 的良好兼容性。为了提高部署效…...