KMP算法中的next数组求解

这篇具有很好参考价值的文章主要介绍了KMP算法中的next数组求解。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

        KMP算法(Knuth-Morris-Pratt) 是一个字符串的匹配算法,其中有一部分算法需要求解next数组来求解该位置前面字符串的最长相同的真前缀和真后缀长度。

        next数组的求解方法为:第一位的next值为0,第二位的next值为1,后面求解每一位的next值时,根据前一位进行比较。首先将前一位与其next值对应的内容进行比较,如果相等,则该位的next值就是前一位的next值加上1;如果不等,向前继续寻找next值对应的内容来与前一位进行比较,直到找到某个位上内容的next值对应的内容与前一位相等为止,则这个位对应的值加上1即为需求的next值;如果找到第一位都没有找到与前一位相等的内容,那么需求的位上的next值即为1。
 

         还是有点难看懂,举个例子:求解模式串 "ababaaabbaa "的next数组,首先先画一个表格便于观察其中的奥秘。在这之前我们要知道模式串中前两个位的next值分别为0,1。

        KMP算法中的next数组求解         先为模式串构建这样一张表,其中第一位和第二位的next值先填入0和1,接下来计算第三位(即下标为3的数据'a')的next值。

        第三位:首先看第三位的前一位即第二位的值(在上面的例子中,这个值为'b'),然后再看第二位的next值,该next值作为下标值找到对应的元素,比较第二位的值是否和这个下标对应的值相等,可以看出第二位的next值对应的值是'a',显然a不等于b,而a的next值已经没有对应的下标元素了,即已经没有下标为0的元素了,因此第三位的next值为1(如果找到最前面也没有找到相等的元素那么所求的next值就为1)。

KMP算法中的next数组求解

 

         第四位:和第三位的求解方法一样,先看第四位的前一位即第三位的值为a,再将第三位的next值作为下标值对应到表中找出对应的元素,比较该元素是否与第四位的前一位的元素相同,如果相同那么第四位的next值就是前一位的next+1。显然第三位的next值作为下标对应的值也为a,两者相等,因此第四位的next值为第三位的next值+1=2。

KMP算法中的next数组求解

        第五位:和之前的方法一样,将第四位的next值作为下标值找对应的值来与第四位的值(a)相比是否相等,正好,第四位next值对应的下标的元素也是b,所以第五位的next值为第四位的next值+1=3。

KMP算法中的next数组求解

 

        第六位:相同的方法,将第五位的next值作为下标找到对应的元素,比较是否与第五位的值相等,很凑巧,也相等,所以第六位的next值为第五位的next值+1=4。

KMP算法中的next数组求解

 

        第七位:将第六位的next值(4)作为下标值找到对应的值,这次发现第六位的值是'a',但是下标为4对应的值是'b',两者不相等,所以再将下标为4的next值(2)再作为下标值找对应的值,再比较是否和第六位的值相等,显然下标为2的值还是'b',与第六位的'a'不相等,因此再将下标为二的next值再作为下标值比较对应的值是否与第六位的值相等,这次发现下标为1的值和第六位相等了,所以第七位的next值就等于第二位的next值+1=2,因为最后是从第二位的next值找到第一位的。也可以看作是第七位的next值等于第一位的 下标值+1。

 

KMP算法中的next数组求解

        第八位:将第七位的next值作为下标找到对应的值2,与第七位的值'a'做比较,发现不相等,于是将第二位的next值作为下标找到对应值,两者相等都为a,所以第八位的next值=第二位的next值+1=2。

KMP算法中的next数组求解 

         第九位:将第八位的next值作为下标值找到对应的值,比较是否与第八位的值相等,这次发现相等了,因为第八位的next值(2)作为下标对应的值也是b,因此第九位的next值=第八位的next值+1=3。

KMP算法中的next数组求解

         第十位:将第九位的next值作为下标找到对应的值,再比较,发现两者都为a,因此第九位的next值=第八位的next值+1=4。

KMP算法中的next数组求解

        第十一位:将第十位的next值作为下标找到对应的值进行比较,发现两者相等,因此第十一位的next=第十位的next+1=5。

KMP算法中的next数组求解 

        第十二位: 将第十一位的next值作为下标找到对应的值进行比较,发现两者相等,因此第十二位的next=第十一位的next+1=6。

KMP算法中的next数组求解

         所以该字符串的next数组为:011234223456文章来源地址https://www.toymoban.com/news/detail-498967.html

到了这里,关于KMP算法中的next数组求解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】字符串匹配|BF算法|KMP算法|next数组的优化

    字符串匹配算法是在实际工程中经常遇到的问题,也是各大公司笔试面试的常考题目,本文主要介绍BF算法(最好想到的算法,也最好实现)和KMP算法(最经典的) BF算法,即暴力(Brute Force)算法,是普通的模式匹配算法,BF算法的思想就是将目标S的第一个字符与模式串T的第一

    2024年02月04日
    浏览(56)
  • C语言数据结构+KMP算法next数组优化计算方法+优化后子串匹配代码实现

    通过我之前那篇KMP算法的讲解,我们可以快速手算KMP算法的next数组,但是之前计算的next数组在一些情况下会有缺陷,比如模式串’aaaab’和主串’aaabaaaab’进行匹配 令模式串指针为j 当第一个元素不匹配时,下一次匹配还是要从模式串的第一个元素与主串匹配,其实我们可以直接写

    2024年02月06日
    浏览(54)
  • 【KMP】从原理上详解next数组和nextval数组

    本文将从原理上详细解释KMP算法中的 next 数组以及 nextval 数组,尽量让大家明白它们到底在记录什么,为什么要这样算。以及 现在普遍的KMP算法实现当中的next数组与前两者有何不同 。篇幅较长,但尽量讲清楚。 虽然数据结构中对next数组有定义,但并不易于理解,因此我个

    2024年02月06日
    浏览(47)
  • 【LeetCode.384打乱数组】Knuth洗牌算法详解

    前两天看网易面筋得知网易云的随机歌曲播放使用了这个算法,遂找题来做做学习一下 https://leetcode.cn/problems/shuffle-an-array/ 给你一个整数数组 nums ,设计算法来打乱一个没有重复元素的数组。打乱后,数组的所有排列应该是 等可能 的。 实现 Solution class: Solution(int[] nums) 使用

    2024年02月08日
    浏览(36)
  • 图解KMP算法,带你彻底吃透KMP

    KMP算法 一直是一个比较难以理解的算法,本篇文章主要根据《大话数据结构》中关于KMP算法的讲解,结合自己的思考,对于KMP算法进行一个比较详细的解释。 由于博主本人水平有限,难免会出现一些错误。如果发现文章中存在错误敬请批评指正,感谢您的阅读。 字符串模式

    2024年02月08日
    浏览(54)
  • 【算法思维】-- KMP算法

    OJ须知: 一般而言,OJ在1s内能接受的算法时间复杂度:10e8 ~ 10e9之间(中值5*10e8)。在竞赛中, 一般认为计算机1秒能执行 5*10e8 次计算 。 时间复杂度 取值范围 o(log2n) 大的离谱 O(n) 10e8 O(nlog(n)) 10e6 O(nsqrt(n))) 10e5 O(n^2) 5000 O(n^3) 300 O(2^n) 25 O(3^n) 15 O(n!) 11 时间复杂度排序: o(1)

    2024年02月06日
    浏览(47)
  • 算法:数组中的最大差值---“打擂台法“

    文章来源: https://blog.csdn.net/weixin_45630258/article/details/132737088 欢迎各位大佬指点、三连 1、题目: 给定一个整数数组 nums,找出给定数组中两个数字之间的最大差值。要求,第二个数字必须大于第一个数字。 2、 分析特点: 求最大差值 == 最大值 - 最小值 只需要遍历价格数组一

    2024年02月09日
    浏览(43)
  • 剑指offer中算法:二维数组中的查找

    在一个 n * m 的二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个高效的函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。 示例 现有矩阵 matrix 如下: { {1, 4, 7}, {2, 5, 8,}, {3, 6, 9} } 给定 target = 9,

    2024年02月12日
    浏览(44)
  • 优化|求解非凸和无梯度lipschitz连续性的一阶算法在二次规划反问题中的应用(代码分享)

    原文信息(包括题目、发表期刊、原文链接等):First Order Methods Beyond Convexity and Lipschitz Gradient Continuity with Applications to Quadratic Inverse Problems 原文作者:Jérôme Bolte, Shoham Sabach, Marc Teboulle, and Yakov Vaisbourd 代码分享者:李朋 考虑下面的二次规划反问题 min ⁡ { Ψ ( x ) : = g ( x ) +

    2024年02月05日
    浏览(45)
  • 算法:删除有序数组中的重复项---双指针[3]

    文章来源: https://blog.csdn.net/weixin_45630258/article/details/132701024 欢迎各位大佬指点、三连 1、题目: 对给定的有序数组 nums 删除重复元素,在删除重复元素之后,每个元素只出现一次,并返回新的长度,上述操作必须通过 原地修改 数组的方法,使用 O(1) 的空间复杂度完成。 2、

    2024年02月09日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包