数据结构(邓俊辉)学习笔记】串 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

相关文章

MySQL 中的 JSON 查询案例详解

《MySQL中的JSON查询案例详解》:本文主要介绍MySQL的JSON查询的相关知识,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录mysql 的 jsON 路径格式基本结构路径组件详解特殊语法元素实际示例简单路径复杂路径简写操作符注意MySQL 的 J

Java学习手册之Filter和Listener使用方法

《Java学习手册之Filter和Listener使用方法》:本文主要介绍Java学习手册之Filter和Listener使用方法的相关资料,Filter是一种拦截器,可以在请求到达Servl... 目录一、Filter(过滤器)1. Filter 的工作原理2. Filter 的配置与使用二、Listen

Go语言开发实现查询IP信息的MCP服务器

《Go语言开发实现查询IP信息的MCP服务器》随着MCP的快速普及和广泛应用,MCP服务器也层出不穷,本文将详细介绍如何在Go语言中使用go-mcp库来开发一个查询IP信息的MCP... 目录前言mcp-ip-geo 服务器目录结构说明查询 IP 信息功能实现工具实现工具管理查询单个 IP 信息工具的实现服

MySQL索引的优化之LIKE模糊查询功能实现

《MySQL索引的优化之LIKE模糊查询功能实现》:本文主要介绍MySQL索引的优化之LIKE模糊查询功能实现,本文通过示例代码给大家介绍的非常详细,感兴趣的朋友一起看看吧... 目录一、前缀匹配优化二、后缀匹配优化三、中间匹配优化四、覆盖索引优化五、减少查询范围六、避免通配符开头七、使用外部搜索引擎八、分

SQL表间关联查询实例详解

《SQL表间关联查询实例详解》本文主要讲解SQL语句中常用的表间关联查询方式,包括:左连接(leftjoin)、右连接(rightjoin)、全连接(fulljoin)、内连接(innerjoin)、... 目录简介样例准备左外连接右外连接全外连接内连接交叉连接自然连接简介本文主要讲解SQL语句中常用的表

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

MySQL高级查询之JOIN、子查询、窗口函数实际案例

《MySQL高级查询之JOIN、子查询、窗口函数实际案例》:本文主要介绍MySQL高级查询之JOIN、子查询、窗口函数实际案例的相关资料,JOIN用于多表关联查询,子查询用于数据筛选和过滤,窗口函... 目录前言1. JOIN(连接查询)1.1 内连接(INNER JOIN)1.2 左连接(LEFT JOI

MySQL 中查询 VARCHAR 类型 JSON 数据的问题记录

《MySQL中查询VARCHAR类型JSON数据的问题记录》在数据库设计中,有时我们会将JSON数据存储在VARCHAR或TEXT类型字段中,本文将详细介绍如何在MySQL中有效查询存储为V... 目录一、问题背景二、mysql jsON 函数2.1 常用 JSON 函数三、查询示例3.1 基本查询3.2

MySQL中的交叉连接、自然连接和内连接查询详解

《MySQL中的交叉连接、自然连接和内连接查询详解》:本文主要介绍MySQL中的交叉连接、自然连接和内连接查询,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、引入二、交php叉连接(cross join)三、自然连接(naturalandroid join)四

mysql的基础语句和外键查询及其语句详解(推荐)

《mysql的基础语句和外键查询及其语句详解(推荐)》:本文主要介绍mysql的基础语句和外键查询及其语句详解(推荐),本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋... 目录一、mysql 基础语句1. 数据库操作 创建数据库2. 表操作 创建表3. CRUD 操作二、外键