数据结构面试常见问题之串的模式匹配(KMP算法)系列-大师改进

😀前言
KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt提出,因此人们称它为克努特—莫里斯—普拉特操作(简称KMP算法)

KMP算法的优势:

提高了匹配效率,时间复杂度为O(m+n),其中m为模式串长度,n为主串长度。
克服了朴素算法的回溯问题,减少了不必要的比较次数。

🏠个人主页:尘觉主页

文章目录

  • 数据结构面试常见问题之串的模式匹配(KMP算法)系列-大师改进
    • KMP-2. KMP 算法思路
      • 大师改进
      • 模式匹配类型
    • 😄总结
      • KMP算法思路
      • next数组的含义:
      • 大师改进:KMP算法
      • 改进后的next数组计算方法:
      • 总结

数据结构面试常见问题之串的模式匹配(KMP算法)系列-大师改进

KMP-2. KMP 算法思路

大师改进

方法3:KMP(Knuth、Morris、Pratt)算法

T = O(n+m)
简单的往前错一位的比较是完全没有必要的没有意义的,如下图
在这里插入图片描述
KMP算法的想法:
在这里插入图片描述
指针指向x不会回退(回溯)了,直接继续从x开始,继续往前比较
在这里插入图片描述
match的具体例子
在这里插入图片描述

下标从090个字符对应的是一个长度为1的子串,所以他不可能产生匹配,match就永远是-101:a跟b是配不上的,match也为-1
0-2:a和c配不上,ab和bc也配不上,所以match还是为-1
0-3:ab和ca是配不上的,abc跟bca也配不上,a对应的j为0,所以match也为0
//此时限制条件是最大i是小于j的,如果i=j的话那就相当于自己等于自己就没有意义了(p0...pj =p0...pj)
//所以我们考虑他的真子串
0-4:a跟b配不上,abc跟cab配不上,ab跟ab能配上,match值为1...

对于 pattern = abcabcacab,最后 3 个字符的 match 值是多少?-1, 0, 1
在早期的教科书上被叫做failure(失败的意思)

match值的含义:
例子:从0到6的子串,首跟尾能配上的小串,从0开始他的尾部下标为3,abca跟abca能配上。这就是match的含义

此代码块内容来自百度百科:
KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt提出的,因此人们称它为克努特—莫里斯—普拉特操作(简称KMP算法)。KMP算法的核心是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现,函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n)
KMP算法是三位学者在 Brute-Force算法的基础上同时提出的模式匹配的改进算法。Brute- Force算法在模式串中有多个字符和主串中的若干个连续字符比较都相等,但最后一个字符比较不相等时,主串的比较位置需要回退。KMP算法在上述情况下,主串位置不需要回退,从而可以大大提高效率

模式匹配类型

(1)精确匹配
如果在目标T中至少一处存在模式P,则称匹配成功,否则即使目标与模式只有一个字符不同也不能称为匹配成功,即匹配失败。给定一个字符或符号组成的字符串目标对象T和一个字符串模式P,模式匹配的目的是在目标T中搜索与模式P完全相同的子串,返回T和P匹配的第一个字符串的首字母位置 。
(2)近似匹配
如果模式P与目标T(或其子串)存在某种程度的相似,则认为匹配成功。常用的衡量字符串相似度的方法是根据一个串转换成另一个串所需的基本操作数目来确定。基本操作由字符串的插入、删除和替换来组成

第一篇–>数据结构面试常见问题之串的模式匹配(KMP算法)系列-简单解决方案

第二篇–>数据结构面试常见问题之串的模式匹配(KMP算法)系列-大师改进

第三篇–>数据结构面试常见问题之串的模式匹配(KMP算法)系列-大师改进实现以及原理

😄总结

KMP算法思路

KMP算法的核心思想是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数。具体来说,KMP算法通过一个next数组记录模式串的部分匹配信息,当主串与模式串匹配失败时,可以根据next数组直接跳转到模式串中下一个可能匹配的位置,避免回溯。

next数组的含义:

next[j]表示模式串P的前j个字符(不包括第j个字符)与P的后缀中最长的公共前缀的长度。

举个例子:

模式串P = “ABCDABD”

next[0] = -1 (空串与任何字符串都没有公共前缀)

next[1] = 0 (A与空串的公共前缀是空串)

next[2] = 0 (AB与A的公共前缀是A)

next[3] = 1 (ABC与AB的公共前缀是AB)

next[4] = 2 (ABCD与ABC的公共前缀是ABC)

next[5] = 3 (ABCDAB与ABCD的公共前缀是ABCD)

next[6] = 2 (ABCDABD与ABCDAB的公共前缀是ABCDAB)

大师改进:KMP算法

KMP算法的核心改进在于next数组的计算。朴素的next数组计算方法是逐个计算每个next[j]的值,时间复杂度为O(m^2)。KMP算法通过改进next数组的计算方法,将时间复杂度降低到O(m)。

改进后的next数组计算方法:

初始化next[0] = -1
从j = 1开始循环
若P[j] = P[next[j-1]],则next[j] = next[j-1] + 1
若P[j] != P[next[j-1]],则
若next[j-1] != -1,则令j = next[j-1],并重复步骤3
若next[j-1] == -1,则next[j] = 0

总结

KMP算法是字符串匹配领域的重要算法,具有广泛的应用价值。KMP算法的核心思想是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数,从而提高匹配效率。

😁热门专栏推荐
想学习vue的可以看看这个

java基础合集

数据库合集

redis合集

nginx合集

linux合集

手写机制

微服务组件

spring_尘觉

springMVC

mybits

等等等还有许多优秀的合集在主页等着大家的光顾感谢大家的支持

🤔欢迎大家加入我的社区 尘觉社区

文章到这里就结束了,如果有什么疑问的地方请指出,诸佬们一起来评论区一起讨论😁
希望能和诸佬们一起努力,今后我们一起观看感谢您的阅读🍻
如果帮助到您不妨3连支持一下,创造不易您们的支持是我的动力🤞

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/493787.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

力扣面试150 移除元素 双指针

Problem: 27. 移除元素 思路 &#x1f468;‍&#x1f3eb; 三叶题解 复杂度 时间复杂度: O ( n ) O(n) O(n) 空间复杂度: O ( 1 ) O(1) O(1) Code class Solution {public int removeElement(int[] nums, int val) {int j nums.length - 1;for (int i 0; i < j;…

Netty服务端基本启动流程源码刨析

前言: 希望看这篇文章之前对Java Nio编程比较熟悉&#xff0c;并有用过Netty开发简单代码 服务端代码 先大致说一下NioEventLoopGroup组件的作用&#xff0c;可以把它看是作内部维护了一个NioEventLoop数组的对象&#xff0c;它的构造方法的参数用来指定维护数组的大小。NioEve…

快速上手Spring Cloud 十:Spring Cloud与微前端

快速上手Spring Cloud 一&#xff1a;Spring Cloud 简介 快速上手Spring Cloud 二&#xff1a;核心组件解析 快速上手Spring Cloud 三&#xff1a;API网关深入探索与实战应用 快速上手Spring Cloud 四&#xff1a;微服务治理与安全 快速上手Spring Cloud 五&#xff1a;Spring …

强化基础-Java-泛型

什么是泛型&#xff1f; 泛型其实就参数化类型&#xff0c;也就是说这个类型类似一个变量是可变的。 为什么会有泛型&#xff1f; 在没有泛型之前&#xff0c;java中是通过Object来实现泛型的功能。但是这样做有下面两个缺陷&#xff1a; 1 获取值的时候必须进行强转 2 没有…

Learn OpenGL 26 视差贴图

什么是视差贴图 视差贴图(Parallax Mapping)技术和法线贴图差不多&#xff0c;但它有着不同的原则。和法线贴图一样视差贴图能够极大提升表面细节&#xff0c;使之具有深度感。它也是利用了视错觉&#xff0c;然而对深度有着更好的表达&#xff0c;与法线贴图一起用能够产生难…

商标跨类异议与跨类保护!

有个朋友对普推知产老杨说收到某邮件&#xff0c;名下商标让某公司抢注了现在公告期&#xff0c;让赶紧提出来异议去处理下&#xff0c;怎么会有这样的事&#xff0c;相同的名称基本上在同类别相关产品是无法公告和获得初审的。 经详细检索分析后&#xff0c;发现不是这样一回…

【Linux】理解父子进程(系统调用创建进程,fork函数,写时拷贝)

目录 fork函数 返回值 内存分配 父子进程是操作系统一个重要的概念&#xff0c;特别是在多任务处理和并发编程中&#xff0c;在Linux中&#xff0c;每个进程都有一个唯一的进程ID&#xff0c;并且每个进程都有可能创建其他进程。当一个进程创建了一个新的进程时&#xff0c;…

【Linux】进程>环境变量地址空间进程调度

主页&#xff1a;醋溜马桶圈-CSDN博客 专栏&#xff1a;Linux_醋溜马桶圈的博客-CSDN博客 gitee&#xff1a;mnxcc (mnxcc) - Gitee.com 目录 1.环境变量 1.1 基本概念 1.2 常见环境变量 1.3 查看环境变量方法 1.4 和环境变量相关的命令 1.5 环境变量的组织方式 1.6 通…

最“原始”的收音机长啥样?

同学们大家好&#xff0c;今天我们继续学习杨欣的《电子设计从零开始》&#xff0c;这本书从基本原理出发&#xff0c;知识点遍及无线电通讯、仪器设计、三极管电路、集成电路、传感器、数字电路基础、单片机及应用实例&#xff0c;可以说是全面系统地介绍了电子设计所需的知识…

vs code

vs code 下载安装 https://code.visualstudio.com/https://code.visualstudio.com/ 下载完后&#xff0c;下一步下一步就安装完了&#xff0c;安装好后可以下载各种好用的插件

【前端面试3+1】03深拷贝浅拷贝、let和var、css盒模型、【有效括号】

一、深拷贝浅拷贝 深拷贝和浅拷贝都是用于复制对象或数组的概念&#xff0c;但它们之间有着重要的区别&#xff1a; 1. 浅拷贝&#xff1a; 浅拷贝是指在拷贝对象或数组时&#xff0c;只会复制一层对象的属性或元素&#xff0c;而不会递归地复制嵌套的对象或数组。因此&#xf…

2024年第十二届计算机与通信管理国际会议(ICCCM 2024)即将召开!

2024年第十二届计算机与通信管理国际会议&#xff08;ICCCM 2024&#xff09;将2024年7月19-21日在日本鹿儿岛召开。会议由鹿儿岛大学主办。此次会议旨在为业界建立一个广泛、有效的交流合作平台&#xff0c;让我们及时了解行业发展动态、掌握最新技术&#xff0c;拓宽研究视野…

修改Jupyter Notebook的默认路径,以及在PowerShell中自定义其启动路径

修改Jupyter Notebook的默认路径&#xff0c;以及在PowerShell中自定义其启动路径 设置 Jupyter Notebook 配置文件&#xff0c;修改默认路径要在PowerShell中设置自定义的启动脚本&#xff0c;以确保Jupyter Notebook能够自动定位到当前路径设置后的效果 在使用Jupyter Notebo…

【C语言】编译和链接

文章目录 一、编译环境和运行环境二、翻译环境2.1 预处理2.2 编译2.2.1 词法分析2.2.2 语法分析2.2.3 语义分析 2.3 汇编2.4 链接 三、运行环境 一、编译环境和运行环境 在ANSIC的任何一种实现中&#xff0c;存在两个不同的环境。 第1种是翻译环境&#xff0c;在这个环境中源代…

C++ STL教程

C STL教程 文章目录 C STL教程1.1 std::vector1.1.1vector的定义1.1.2vector容器的初始化1.1.3vector容器内元素的访问和修改1.1.4vector中的常用函数 1.2 std::string1.2.1string的定义1.2.2string的初始化1.2.3string中元素的访问和修改1.2.4string中连接字符串1.2.5string中…

阿里云服务器安装MySQL(宝塔面板)

只写关键步骤 1. 创建一个云服务器实例 2 修改密码&#xff0c;登录服务器 3. 安装宝塔面板 进入https://www.bt.cn/new/index.html 进入宝塔面板地址 4. 安装Mysql 5. 创建数据库&#xff08;可导入数据库&#xff09; 6. 测试连接数据库 打开Navicat&#xff08;或其他数据…

[Qt] QString::fromLocal8Bit 的使用误区

QString::fromLocal8Bit 是一个平台相关的函数。默认情况下在 Windows 下 就是 gbk 转 utf-8 ,在 Linux就应该是无事发生。因为Linux平台默认的编码方式就是 utf-8 可以通过 void QTextCodec::setCodecForLocale(QTextCodec *c)来修改 Qt默认的编码方式。如下 第一输出乱码的…

DreamPolisher、InternLM2 、AniArtAvatar、PlainMamba、AniPortrait

本文首发于公众号&#xff1a;机器感知 DreamPolisher、InternLM2 、AniArtAvatar、PlainMamba、AniPortrait DreamPolisher: Towards High-Quality Text-to-3D Generation via Geometric Diffusion We present DreamPolisher, a novel Gaussian Splatting based method wit…

kubernetes负载均衡资源-Ingress

一、Ingress概念 1.1 Ingress概念 使用NodePort类型的Service可以将集群内部服务暴露给集群外部客广端,但使用这种类型Service存在如下几个问题。 1、一个端口只能一个服务使用,所有通过NodePort暴露的端口都需要提前规划;2、如果通过NodePort暴露端口过多,后期维护成本太…