数据结构与算法之美学习笔记:34 | 字符串匹配基础(下):如何借助BM算法轻松理解KMP算法?

这里写自定义目录标题

  • 前言
  • KMP 算法基本原理
  • 失效函数计算方法
  • KMP 算法复杂度分析
  • 解答开篇 & 内容小结

前言

在这里插入图片描述
本节课程思维导图:
在这里插入图片描述
BM 算法,是工程中非常常用的一种高效字符串匹配算法。不过,在所有的字符串匹配算法里,要说最知名的一种的话,那就非 KMP 算法莫属。很多时候,提到字符串匹配,我们首先想到的就是 KMP 算法。
实际上,KMP 算法跟 BM 算法的本质是一样的。上一节,我们讲了好后缀和坏字符规则,今天,我们就看下,如何借助上一节 BM 算法的讲解思路,让你能更好地理解 KMP 算法?

KMP 算法基本原理

KMP 算法是根据三位作者(D.E.Knuth,J.H.Morris 和 V.R.Pratt)的名字来命名的,算法的全称是 Knuth Morris Pratt 算法,简称为 KMP 算法。
KMP 算法的核心思想,跟 BM 算法非常相近。我们假设主串是 a,模式串是 b。在模式串与主串匹配的过程中,当遇到不可匹配的字符的时候,我们希望找到一些规律,可以将模式串往后多滑动几位,跳过那些肯定不会匹配的情况。
KMP 算法中,在模式串和主串匹配的过程中,把不能匹配的那个字符仍然叫作坏字符,把已经匹配的那段字符串叫作好前缀。
在这里插入图片描述
当遇到坏字符的时候,我们就要把模式串往后滑动,在滑动的过程中,只要模式串和好前缀有上下重合,前面几个字符的比较,就相当于拿好前缀的后缀子串,跟模式串的前缀子串在比较。
在这里插入图片描述
KMP 算法就是在试图寻找一种规律:在模式串和主串匹配的过程中,当遇到坏字符后,对于已经比对过的好前缀,能否找到一种规律,将模式串一次性滑动很多位?
我们只需要拿好前缀本身,在它的后缀子串中,查找最长的那个可以跟好前缀的前缀子串匹配的。假设最长的可匹配的那部分前缀子串是{v},长度是 k。我们把模式串一次性往后滑动 j-k 位,相当于,每次遇到坏字符的时候,我们就把 j 更新为 k,i 不变,然后继续比较。
在这里插入图片描述
我把好前缀的所有后缀子串中,最长的可匹配前缀子串的那个后缀子串,叫作最长可匹配后缀子串;对应的前缀子串,叫作最长可匹配前缀子串。
在这里插入图片描述
如何来求好前缀的最长可匹配前缀和后缀子串呢?我发现,这个问题其实不涉及主串,只需要通过模式串本身就能求解。所以,我就在想,能不能事先预处理计算好,在模式串和主串匹配的过程中,直接拿过来就用呢?
似 BM 算法中的 bc、suffix、prefix 数组,KMP 算法也可以提前构建一个数组,用来存储模式串中每个前缀(这些前缀都有可能是好前缀)的最长可匹配前缀子串的结尾字符下标。我们把这个数组定义为 next 数组,很多书中还给这个数组起了一个名字,叫失效函数(failure function)。
数组的下标是每个前缀结尾字符下标,数组的值是这个前缀的最长可以匹配前缀子串的结尾字符下标。这句话有点拗口,我举了一个例子,你一看应该就懂了。
在这里插入图片描述
有了 next 数组,我们很容易就可以实现 KMP 算法了。我先假设 next 数组已经计算好了,先给出 KMP 算法的框架代码。

// a, b分别是主串和模式串;n, m分别是主串和模式串的长度。
public static int kmp(char[] a, int n, char[] b, int m) {
  int[] next = getNexts(b, m);
  int j = 0;
  for (int i = 0; i < n; ++i) {
    while (j > 0 && a[i] != b[j]) { // 一直找到a[i]和b[j]
      j = next[j - 1] + 1;
    }
    if (a[i] == b[j]) {
      ++j;
    }
    if (j == m) { // 找到匹配模式串的了
      return i - m + 1;
    }
  }
  return -1;
}

失效函数计算方法

KMP 算法的基本原理讲完了,我们现在来看最复杂的部分,也就是 next 数组是如何计算出来的?当然,我们可以用非常笨的方法,比如要计算下面这个模式串 b 的 next[4],我们就把 b[0, 4]的所有后缀子串,从长到短找出来,依次看看,是否能跟模式串的前缀子串匹配。很显然,这个方法也可以计算得到 next 数组,但是效率非常低。有没有更加高效的方法呢?
在这里插入图片描述
这里的处理非常有技巧,类似于动态规划。我们按照下标从小到大,依次计算 next 数组的值。当我们要计算 next[i]的时候,前面的 next[0],next[1],……,next[i-1]应该已经计算出来了。利用已经计算出来的 next 值,我们是否可以快速推导出 next[i]的值呢?
如果 next[i-1]=k-1,也就是说,子串 b[0, k-1]是 b[0, i-1]的最长可匹配前缀子串。如果子串 b[0, k-1]的下一个字符 b[k],与 b[0, i-1]的下一个字符 b[i]匹配,那子串 b[0, k]就是 b[0, i]的最长可匹配前缀子串。所以,next[i]等于 k。但是,如果 b[0, k-1]的下一字符 b[k]跟 b[0, i-1]的下一个字符 b[i]不相等呢?这个时候就不能简单地通过 next[i-1]得到 next[i]了。这个时候该怎么办呢?
在这里插入图片描述
我们假设 b[0, i]的最长可匹配后缀子串是 b[r, i]。如果我们把最后一个字符去掉,那 b[r, i-1]肯定是 b[0, i-1]的可匹配后缀子串,但不一定是最长可匹配后缀子串。所以,既然 b[0, i-1]最长可匹配后缀子串对应的模式串的前缀子串的下一个字符并不等于 b[i],那么我们就可以考察 b[0, i-1]的次长可匹配后缀子串 b[x, i-1]对应的可匹配前缀子串 b[0, i-1-x]的下一个字符 b[i-x]是否等于 b[i]。如果等于,那 b[x, i]就是 b[0, i]的最长可匹配后缀子串。
在这里插入图片描述
可是,如何求得 b[0, i-1]的次长可匹配后缀子串呢?次长可匹配后缀子串肯定被包含在最长可匹配后缀子串中,而最长可匹配后缀子串又对应最长可匹配前缀子串 b[0, y]。于是,查找 b[0, i-1]的次长可匹配后缀子串,这个问题就变成,查找 b[0, y]的最长匹配后缀子串的问题了。
在这里插入图片描述

// b表示模式串,m表示模式串的长度
private static int[] getNexts(char[] b, int m) {
  int[] next = new int[m];
  next[0] = -1;
  int k = -1;
  for (int i = 1; i < m; ++i) {
    while (k != -1 && b[k + 1] != b[i]) {
      k = next[k];
    }
    if (b[k + 1] == b[i]) {
      ++k;
    }
    next[i] = k;
  }
  return next;
}

KMP 算法复杂度分析

我们现在来分析一下 KMP 算法的时间、空间复杂度是多少?
空间复杂度很容易分析,KMP 算法只需要一个额外的 next 数组,数组的大小跟模式串相同。所以空间复杂度是 O(m),m 表示模式串的长度。
KMP 算法包含两部分,第一部分是构建 next 数组,第二部分才是借助 next 数组匹配。所以,关于时间复杂度,我们要分别从这两部分来分析。
我们先来分析第一部分的时间复杂度。
我们可以找一些参照变量,i 和 k。i 从 1 开始一直增加到 m,而 k 并不是每次 for 循环都会增加,所以,k 累积增加的值肯定小于 m。而 while 循环里 k=next[k],实际上是在减小 k 的值,k 累积都没有增加超过 m,所以 while 循环里面 k=next[k]总的执行次数也不可能超过 m。因此,next 数组计算的时间复杂度是 O(m)。
我们再来分析第二部分的时间复杂度。分析的方法是类似的。
i 从 0 循环增长到 n-1,j 的增长量不可能超过 i,所以肯定小于 n。而 while 循环中的那条语句 j=next[j-1]+1,不会让 j 增长的,那有没有可能让 j 不变呢?也没有可能。因为 next[j-1]的值肯定小于 j-1,所以 while 循环中的这条语句实际上也是在让 j 的值减少。而 j 总共增长的量都不会超过 n,那减少的量也不可能超过 n,所以 while 循环中的这条语句总的执行次数也不会超过 n,所以这部分的时间复杂度是 O(n)。
所以,综合两部分的时间复杂度,KMP 算法的时间复杂度就是 O(m+n)。

解答开篇 & 内容小结

KMP 算法和BM 算法的本质非常类似,都是根据规律在遇到坏字符的时候,把模式串往后多滑动几位。
BM 算法有两个规则,坏字符和好后缀。KMP 算法借鉴 BM 算法的思想,可以总结成好前缀规则。这里面最难懂的就是 next 数组的计算。如果用最笨的方法来计算,确实不难,但是效率会比较低。所以,我讲了一种类似动态规划的方法,按照下标 i 从小到大,依次计算 next[i],并且 next[i]的计算通过前面已经计算出来的 next[0],next[1],……,next[i-1]来推导。
KMP 算法的时间复杂度是 O(n+m)。

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

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

相关文章

毫米波雷达天线罩设计指导2(TI文档)

5 天线罩设计与仿真 本节重点介绍了一些天线罩设计和仿真&#xff0c;IWR6843 ISK型天线使用球形天线罩作为案例研究。在本节中&#xff0c;将比较带和不带天线罩的远场天线辐射方向图。在这次仿真中&#xff0c;使用了IWR6843 ISK EVM设计的衍生品。 图5-1 ~图5-4为三维电磁场…

Redis分布式缓存超详细总结!

文章目录 前言一、Redis持久化解决数据丢失问题1.RDB&#xff08;Redis Database Backup file&#xff09;持久化&#xff08;1&#xff09;执行RDB&#xff08;2&#xff09;RDB方式bgsave的基本流程&#xff08;3&#xff09;RDB会在什么时候执行&#xff1f;save 60 1000代表…

大数据:Hadoop刷题

大数据&#xff1a;Hadoop刷题 2022找工作是学历、能力和运气的超强结合体&#xff0c;遇到寒冬&#xff0c;大厂不招人&#xff0c;可能很多算法学生都得去找开发&#xff0c;测开 测开的话&#xff0c;你就得学数据库&#xff0c;sql&#xff0c;oracle&#xff0c;尤其sql要…

YOLOv7保姆级教程(个人踩坑无数)----训练自己的数据集

目录 一、前言&#xff1a; 二、YOLOv7代码下载 三、环境配置 四、测试结果 五、制作自己的数据集 六、训练自己的数据集 一、前言&#xff1a; 上一篇已经详细讲解了如何安装深度学习所需要的环境&#xff0c;这一篇则详细讲解如何配置YOLOv7&#xff0c;在本地电脑或者…

springboot整合xxl-job,通过代码进行调度中心注册开启任务等

背景&#xff1a;由于工作需要&#xff0c;当用户在登录时自动触发定时任务。而不需要我们手动到调度中心管理页面去创建任务。 工程介绍&#xff1a;分为两个项目&#xff0c;第一个是调度中心的项目&#xff08;xxl-job-admin&#xff09;。第二个是我们自己的项目&#xff0…

基于ssm实验室开放管理系统论文

摘 要 现代经济快节奏发展以及不断完善升级的信息化技术&#xff0c;让传统数据信息的管理升级为软件存储&#xff0c;归纳&#xff0c;集中处理数据信息的管理方式。本实验室开放管理系统就是在这样的大环境下诞生&#xff0c;其可以帮助管理者在短时间内处理完毕庞大的数据信…

为什么推荐将静态资源放到CDN上?

一、什么是静态资源 说到静态资源&#xff0c;我们还要知道什么是动态资源 静态资源 静态资源是指在服务器上存储的不经常改变的文件&#xff0c;如图片、CSS 文件、JavaScript 文件、字体文件等。与之相对的是动态资源&#xff0c;动态资源是根据用户请求和服务器端处理生成的…

【后端学前端】第二天 css动画 动感菜单(css变量、过渡动画、过渡延迟、js动态切换菜单)

目录 1、学习信息 2、源码 3、变量 1.1 定义变量 1.2 使用变量 1.3 calc() 函数 4、定位absolute和fixed 5、transform 和 transition&#xff0c;动画 5.1 变形transform 5.2 transition 5.3 动画animation 6、todo 1、学习信息 视频地址&#xff1a;css动画 动感菜…

.9.png的创建

1、创建.9.png 选中图片&#xff0c;右击&#xff0c;选择Create 9-Patch file&#xff0c;点击确定会生成一个xxx.9.png的图片 2、绘制拉伸区域 在图片的最外边界绘制拉伸区域&#xff0c;按住鼠标左键不放&#xff0c;绘制完成后保存就可以使用了。绘制结果示意如下&…

【AI绘画】万字长文——(超详细)ControlNet的详细介绍使用Stable Diffusion的艺术二维码完全生成攻略

目录 前言一、名词解释1-1、Stable Diffusion介绍1-2、ControlNet介绍1-2-1、ControlNet介绍&工作原理1-2-2、ControlNet控制方法介绍 1-3、案例分析1-3-1、室内装修设计1-3-2、品牌创意海报 1-4、stable-diffusion-webui 的参数解释 二、生成方法2-1、图像到图像2-1-1、二…

nodejs微信小程序+python+PHP健身服务应用APP-计算机毕业设计推荐 android

人类的进步带动信息化的发展&#xff0c;使人们生活节奏越来越快&#xff0c;所以人们越来越重视信息的时效性。以往的管理方式已经满足不了人们对获得信息的方式、方便快捷的需求。即健身服务应用APP慢慢的被人们关注。首先&#xff0c;网上获取信息十分的实时、便捷&#xff…

工业级路由器在货运物流仓储管理中的应用

工业级路由器在货运物流仓储管理中扮演着重要的角色&#xff0c;为整个物流系统提供了稳定可靠的网络连接和数据传输支持。下面将从以下几个方面介绍工业级路由器在货运物流仓储管理中的应用。 实时监控和追踪&#xff1a;工业级路由器通过与各种传感器、监控设备和物联网设备的…

高仿互站网站源码 后台手机端两套模板 电脑端二十套模版

源码简介 高仿互站网 后台手机端两套模板 电脑端二十套模版&#xff0c;简单介绍几个功能&#xff0c; 支持用户注册开店 开店申请&#xff0c;支持用户发布自己商品 支持卡密形式或实物形式&#xff0c; 支持用户自己发布求助 任务大厅功能&#xff0c;源码完整

解决火狐浏览器拖拽事件打开新页面的问题

产生原因及解决方案 我们在进行拖拽事件的编写时会发现&#xff0c;在火狐浏览器上会发生打开新窗口的问题&#xff0c;这是火狐浏览器的一个特性。 这是因为在 Firefox 中 ondrop 事件会触发 Firefox 自带的拖拽搜索功能&#xff0c;在 ondrop 事件触发执行时触发的函数中加…

A-23 P离子交换树脂:高效去除无机有机污染物的新选择

在当今水处理行业中&#xff0c;高效、环保的离子交换树脂备受关注。本文将为您介绍一款具有卓越性能的碱性季胺基阴离子交换树脂——Tulsion A-23 P。通过分析其特性和应用&#xff0c;展示其在水处理领域的优势。 一、Tulsion A-23 P离子交换树脂的特性 物理化学稳定性&#…

<习题集><LeetCode><队列><225/232/387/622/641>

目录 225. 用队列实现栈 232. 用栈实现队列 387. 字符串中的第一个唯一字符 622. 设计循环队列 641. 设计循环双端队列 225. 用队列实现栈 https://leetcode.cn/problems/implement-stack-using-queues/ class MyStack{private Queue<Integer> queue1;private Queu…

SQL命令---修改字段的数据类型

介绍 使用sql语句修改字段的数据类型。 命令 alter table 表明 modify 字段名 数据类型;例子 有一张a表&#xff0c;表里有一个id字段&#xff0c;长度为11。使用命令将长度修改为12 下面使用命令进行修改&#xff1a; alter table a modify id int(12) NOT NULL;下面使修…

基于lambda简化设计模式

前言 虽说使用设计模式可以让复杂的业务代码变得清晰且易于维护&#xff0c;但是某些情况下&#xff0c;开发可能会遇到我为了简单的业务逻辑去适配设计模式的情况&#xff0c;本文笔者就以四种常见的设计模式为例&#xff0c;演示如何基于lambda来简化设计模式的实现。 策略…

node.js express JWT token生成与校验

目录 JWT header&#xff08;标头&#xff09; payload&#xff08;有效负载&#xff09; signature&#xff08;签名&#xff09; 访问令牌&#xff08;token&#xff09; express jwt生成、验证 生成jwt 验证jwt JWT JWT 是轻量级的数据交换格式&#xff0c;相对于传…