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

http://www.lryc.cn/news/300980.html

相关文章:

  • ubuntu22.04@laptop OpenCV Get Started: 013_contour_detection
  • [ai笔记5] 个人AI资讯助手实战
  • QT+OSG/osgEarth编译之八十九:osgdb_ply+Qt编译(一套代码、一套框架,跨平台编译,版本:OSG-3.6.5插件库osgdb_ply)
  • 机器人专题:我国机器人产业园区发展现状、问题、经验及建议
  • 算法沉淀——哈希算法(leetcode真题剖析)
  • 深入理解Redis哨兵原理
  • MySQL-存储过程(PROCEDURE)
  • linux系统监控工具prometheus的安装以及监控mysql
  • 初识tensorflow程序设计模式
  • 【QT+QGIS跨平台编译】之三十八:【GDAL+Qt跨平台编译】(一套代码、一套框架,跨平台编译)
  • 黑马鸿蒙教程学习1:Helloworld
  • 蓝桥杯每日一题------背包问题(四)
  • OpenAI发布Sora技术报告深度解读!真的太强了!
  • AJAX——接口文档
  • leetcode hot100不同路径
  • 【前端工程化面试题目】webpack 的热更新原理
  • 不花一分钱,在 Mac 上跑 Windows(M1/M2 版)
  • Attempt to call an undefined function glutInit
  • AB测试最小样本量
  • 在Spring中事务失效的场景
  • Rust 学习笔记 - 变量声明与使用
  • windows 下跑起大模型(llama)操作笔记
  • 人工智能专题:基础设施行业智能化的基础设施,自智网络双价值分析
  • docker 编译安装redis脚本
  • 鸿蒙开发系列教程(二十三)--List 列表操作(2)
  • C#根据权重抽取随机数
  • SORA:OpenAI最新文本驱动视频生成大模型技术报告解读
  • 阿里云第七代云服务器ECS计算c7、通用g7和内存r7配置如何选择?
  • 视觉slam十四讲学习笔记(六)视觉里程计 1
  • PyTorch-线性回归