数据结构(邓俊辉)学习笔记】串 04——KMP算法:查询表

2024-08-26 15:36

本文主要是介绍数据结构(邓俊辉)学习笔记】串 04——KMP算法:查询表,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 1.制表备查
  • 2.主算法
  • 3.实例

1.制表备查

在这里插入图片描述

接下来我们来看看。KMP 算法究竟如何兑现我们刚才所提及的记忆力以及预知力,我们将会看到这种方法非常的便捷与高效,本质上讲,它无非就是构造了一张查询表。

回到我们刚才的问题,在当前这一轮比对,首次失败于 T[i] 与 P[j] 之后,我们应当如何地向后滑动模式串,从而等效地以一个新的 P[j] 来与刚才的 T[i] 对齐,并从这个位置开始继续新一轮的比对。

这里的好消息是,新的这个 P[j] 不仅可以事先确定,而且这个位置仅取决于模式串,而于主串无关。你能看出,为什么与主串没有关系吗?是的,事实上,在这样的一个时刻,主串无非4个部分,也就是文本串的这个前缀以及后缀,再加上在当前这一轮已经匹配的这个子串,以及失配的这个字符。不难看出,这个前缀与后缀对于新的这个 P[j] 字符的确没有任何影响。而这个子串表面上看对它有所影响,但正因为这个子串与模式串的前缀是匹配的,所以与其说这种影响是来自于文本串,不如说最终还是来自于模式串。能否看透这一点,对于我们以下理解KMP 算法至关重要。

既然下一个接替的字符完全取决于模式串自身,由此出发,再进一步地,与其说这个接替的字符是取决于模式串,不如说它取决于被它顶替的此前的那个 P[j]。事实上在一个长度为 m 的模式串中,这样的字符 P[j] 无非 m 种情况。

而 KMP 算法在此处的关键诀窍在于,将所有这 m 种情况事先处理,并且归纳整理为一张查询表。在经过了这样的预处理之后,在后续的各轮比对中,一旦在某一位置 P[j] 处发生失配,我们只需简单地从查询表中取出对应的那一项,并用它来更新此前的 j。

由此可见,这种策略与其说是在借助强大的记忆力,不如说是在事先已经为各种情况准备好了充分的预案。那么基于这种以查询表的形式给出的预案,KMP 算法又是如何具体工作的呢?

2.主算法

在这里插入图片描述

现在就来考察 KMP 的主算法,可以看到,无论接口形式还是算法的主体流程,KMP 与我们此前蛮力算法的版本一都颇为类似。是的,它的确是在版本一的基础上略加修改而得。

尽管在形式上这种改动非常的细微,但是在本质上却有巨大的区别。

  1. 首先,这里增加了一步预处理,也就是构造出我们刚才所说的那份查询表,我们称之为 next 表。正如我们刚才所言,这个构造过程仅仅取决于模式串,而与文本串没有任何关系,因此是名副其实的预处理;
  2. 接下来与蛮力算法一样,我们也需要两个整数 i 和 j ,分别指向文本串和模式串中当前接受比对的那一对字符。
  3. 算法的主体循环也基本类似, if 分支完全一样。差异仅仅体现在 else 分支,可以看到 KMP 算法在失配情况下的处理更为简明。具体来说,只需从查询表中取出 j 所对应的那一项,并且用它来替换此前的 j。请注意,在这种情况下,KMP 并没有修改变量 i,也就是说它依然指向文本串中此前刚刚失配的那个字符。

这样的处理过程可以由上面插图来说明。请再次确认,此时情况也就是在当前的这轮比对中,主串的字符 T[i] 与模式串的字符 P[j] 首次发生了失配,在算法中也就对应于那个 else 分支,在这种情况下,如果此前模式串所对应的那个前缀长度为 j,那么接下来 KMP 算法将会把这个前缀替换为长度为 next [j] 的那个新的前缀,并从刚才适配的那个位置出发,继续下一轮比对。

当然,细心的你可能会发现,相对于蛮力算法,这里的 if 分支也并非完全地一样。是的,在对应的逻辑判断式中,这里新增了一个并列的条件,j < 0。关于这个条件的妙用之处,现在来谈,还为时过早,我们不妨暂且将其搁置起来。

3.实例

在这里插入图片描述

由上可见,KMP算法的核心就在于那张查询表 next。 在分析这张表的具体原理及其构造过程之前,我们不妨先通过一个实例来切实领会这张表的精妙之处。

考察这个由10个字符所构成的模式串,这里我们直接给出其对应的查询表,请关注其中倒数第三个字符 l,它所对应的秩为 j 等于7,而在查询表中,它所对应的 next 值为3。下面我们就来看看这个表项3所对应的含义及其功能。

假定,这就是主串(chinchi*),如果的确轮到这个表项在发挥作用,那么就意味着在当前这一轮比对中,此前的7个字符都应该是成功的。就是说此时的场景必然是这样(主串上面的模式串),具体来说也就是,模式串中的这个字符 l 与文本串中某个不是 l 的字符比对失败。此时针对这种情况,KMP 算法将会如何处置呢?

为便于对比效果,在处置之前,我不妨先为模式串拍摄一张快照,就像这样(chinchilla)。

现在我们手动来执行一下 KMP 算法

  1. 首先,当前的 j 为7指向模式串中的这个字符 l;

  2. 接下来, KMP 将在查询表中取出对应的那一项,并用它来更新 j。我们刚才已经看到这个表象,就是3,这就意味着接下来 KMP 将会用秩为3的那个字符,也就是 n, 来取代刚才的 l,并继续与文本串中此前失配的那个字符级对齐,就像这样。

    此时我们不妨为模式串再拍摄一张快照。

对比前后两张快照,我们会发现,其效果等同于模式串向后移动了4个字符。不难看出,这个4是来自于7和3的差。从另一角度来看,这些等效于 KMP 聪明地排除掉了3个不必要的对齐位置。是的,这 3 个位置都是无需对齐的,因为它们都不具备足以对齐的必要条件。比如它们所对应的首字符都不是模式上的首字符 c。而反过来,KMP通过 next 表选择了字符 n,从某种意义上讲是非常合理的。没错,它使得相对于 n 而言的这个前缀,依然与主串是匹配的。 具体来说,c 依然对应于 c,h 依然对应于 h,而 i 也依然对应于 i。

是的,通过这样一个实例,我们的确已经能够感受到 KMP 算法及其中 next 表的精妙之处,但严格上来说,在这种精妙的背后究竟是什么样的原理呢?

这篇关于数据结构(邓俊辉)学习笔记】串 04——KMP算法:查询表的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


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

相关文章

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》:本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

浅谈mysql的sql_mode可能会限制你的查询

《浅谈mysql的sql_mode可能会限制你的查询》本文主要介绍了浅谈mysql的sql_mode可能会限制你的查询,这个问题主要说明的是,我们写的sql查询语句违背了聚合函数groupby的规则... 目录场景:问题描述原因分析:解决方案:第一种:修改后,只有当前生效,若是mysql服务重启,就会失效;

MySQL多列IN查询的实现

《MySQL多列IN查询的实现》多列IN查询是一种强大的筛选工具,它允许通过多字段组合快速过滤数据,本文主要介绍了MySQL多列IN查询的实现,具有一定的参考价值,感兴趣的可以了解一下... 目录一、基础语法:多列 IN 的两种写法1. 直接值列表2. 子查询二、对比传统 OR 的写法三、性能分析与优化1.

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

mybatis-plus 实现查询表名动态修改的示例代码

《mybatis-plus实现查询表名动态修改的示例代码》通过MyBatis-Plus实现表名的动态替换,根据配置或入参选择不同的表,本文主要介绍了mybatis-plus实现查询表名动态修改的示... 目录实现数据库初始化依赖包配置读取类设置 myBATis-plus 插件测试通过 mybatis-plu

MySQL中实现多表查询的操作方法(配sql+实操图+案例巩固 通俗易懂版)

《MySQL中实现多表查询的操作方法(配sql+实操图+案例巩固通俗易懂版)》本文主要讲解了MySQL中的多表查询,包括子查询、笛卡尔积、自连接、多表查询的实现方法以及多列子查询等,通过实际例子和操... 目录复合查询1. 回顾查询基本操作group by 分组having1. 显示部门号为10的部门名,员

Java进阶学习之如何开启远程调式

《Java进阶学习之如何开启远程调式》Java开发中的远程调试是一项至关重要的技能,特别是在处理生产环境的问题或者协作开发时,:本文主要介绍Java进阶学习之如何开启远程调式的相关资料,需要的朋友... 目录概述Java远程调试的开启与底层原理开启Java远程调试底层原理JVM参数总结&nbsMbKKXJx

mysql关联查询速度慢的问题及解决

《mysql关联查询速度慢的问题及解决》:本文主要介绍mysql关联查询速度慢的问题及解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录mysql关联查询速度慢1. 记录原因1.1 在一次线上的服务中1.2 最终发现2. 解决方案3. 具体操作总结mysql

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.