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

相关文章

HarmonyOS学习(七)——UI(五)常用布局总结

自适应布局 1.1、线性布局(LinearLayout) 通过线性容器Row和Column实现线性布局。Column容器内的子组件按照垂直方向排列,Row组件中的子组件按照水平方向排列。 属性说明space通过space参数设置主轴上子组件的间距,达到各子组件在排列上的等间距效果alignItems设置子组件在交叉轴上的对齐方式,且在各类尺寸屏幕上表现一致,其中交叉轴为垂直时,取值为Vert

Ilya-AI分享的他在OpenAI学习到的15个提示工程技巧

Ilya(不是本人,claude AI)在社交媒体上分享了他在OpenAI学习到的15个Prompt撰写技巧。 以下是详细的内容: 提示精确化:在编写提示时,力求表达清晰准确。清楚地阐述任务需求和概念定义至关重要。例:不用"分析文本",而用"判断这段话的情感倾向:积极、消极还是中性"。 快速迭代:善于快速连续调整提示。熟练的提示工程师能够灵活地进行多轮优化。例:从"总结文章"到"用

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画(下)

【课程链接】 AntV G6:深入图形与图形分组、自定义节点、节点动画(下)_哔哩哔哩_bilibili 本章十吾老师讲解了一个复杂的自定义节点中,应该怎样去计算和绘制图形,如何给一个图形制作不间断的动画,以及在鼠标事件之后产生动画。(有点难,需要好好理解) <!DOCTYPE html><html><head><meta charset="UTF-8"><title>06

学习hash总结

2014/1/29/   最近刚开始学hash,名字很陌生,但是hash的思想却很熟悉,以前早就做过此类的题,但是不知道这就是hash思想而已,说白了hash就是一个映射,往往灵活利用数组的下标来实现算法,hash的作用:1、判重;2、统计次数;

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

活用c4d官方开发文档查询代码

当你问AI助手比如豆包,如何用python禁止掉xpresso标签时候,它会提示到 这时候要用到两个东西。https://developers.maxon.net/论坛搜索和开发文档 比如这里我就在官方找到正确的id描述 然后我就把参数标签换过来