-
2021-01-19 23:35:01
此篇文章总结的 基于kmp中的模式串方式
关于next图解如下
举例:字符串 “ababaa”
索引 0 1 2 3 4 5 字符 a b a b a a next 0 0 1 1 2 3 next定义写法
从索引1位置开始计算,除去第i位置,从0到 i-1,前后缀中最长重复字符长度
备注如果没有前后缀元素只要自己默认为0,如果没有相同元素默认为1
next[0]=0 默认0
next[1] =0 从1位置开始计算 默认为0
next[2] = 1,此时ab, 前后缀中没有公有为1
next[3] = 1,此时aba, 字符串前缀组合a,ab 字符串后缀组合 b,ba;前后公有最长a,所以为1
next[4] = 2,此时abab, 字符串前缀组合a,ab,aba, 字符串后缀组合 b,ab,bab;前后公有最长ab,所以为2
next[5] = 3,此时ababa, 字符串前缀组合a,ab,aba, 字符串后缀组合 b,ab,aba;前后公有最长aba,所以为3
求解代码如下:
/* *@author: 赵秋然 *@date:2021年1月19日 *@description:kmp中next求解 */ void kmp_next(char patt[], int next[]) { int i = 0, j = 1, n = strlen(patt); next[i] = next[j] = 0; while (j < n) { if (i == 0 || patt[i] == patt[j]) { ++i; next[j + 1] = i; ++j; } else { i = next[i]; } } }
nextval求解方法
nextval是在next方式上的升级改进,使得模式串回退跟快速有效,减少next中不必要的比较
索引 0 1 2 3 4 5 字符 a b a b a a next 0 0 1 1 2 3 nextval 0 0 1 0 1 3 计算方式
默认前2位为0
nextval计算方式需要根据next结果
索引2时,元素a,next值为1,索引为1,元素b, a≠b ;nextval[2] = next[2]=1
索引3时,元素b,next值为1,索引为1,元素b, b=b ;nextval[3] = next[1] = 0
索引4时,元素a,next值为2,索引为2,元素a, a=a ;nextval[4] = next[2] = 1
索引5时,元素a,next值为3,索引为3,元素b, a≠b ;nextval[5] = next[5] = 3
根据以上结论得出:
当前索引与next索引值相同,此时索引值为next索引值
如果不同,此时索引值为next值
/* *@author: 赵秋然 *@date:2021年1月21日 *@description:kmp中nextval求解 */ void kmp_nextval(char patt[], int next[]) { int i = 0, j = 1, n = strlen(patt); next[i] = next[j] = 0; while(j < n) { if(i == 0 || patt[i] == patt[j]) { if(patt[j+1] == patt[i+1]) { next[j+1] = next[i+1]; } else { next[j+1] = i+1; } ++i; ++j; } else { i = next[i]; } } }
为什么会引入nextval呢?
举例:
索引 0 1 2 3 4 5 字符 a a a a a b next 0 0 1 2 3 4 nextval 0 0 0 0 0 4 模式串aaaaab,构建next数组后,对字符进行匹配时,如果发现字符不匹配那么next就需要回退
如果此时是索引4位置不匹配,那么根据next值就需要回退到3,2,1的不断回退,匹配速度变慢,效率下降
nextval方式直接回退到首位置,减少了不必要的回退
更多相关内容 -
字符串next值计算方法 附前缀后缀解释
2019-11-17 15:23:03网上看了很多的解析,好多博主抛出一个概念,然后没有解析,对我这种弱渣来说更加懵逼了~下面是我总结的一个简单的计算方法 首先介绍2个概念,字符串的前缀和后缀(这里的前缀是不包括最后一个字符的子串,后缀是不...原题:
大一学的数据结构全忘了,做题看到的,整个人都懵了。。
网上看了很多的解析,好多博主抛出一个概念,然后没有解析,对我这种弱渣来说更加懵逼了~下面是我总结的一个简单的计算方法首先介绍2个概念,字符串的前缀和后缀(这里的前缀是不包括最后一个字符的子串,后缀是不包含第一个字符的子串)。
拿题目中的字符串a=’‘babab’'举例,
首先第一位0,第二位1。这个是固定的。第三位,字符串是“bab”,这时候“bab”的前缀有b,ba;后缀有ab,b,可以看出前后缀相等的最长的字符串只有b,因为b的长度是1,所以这里第三位的next值就是1。
第四位,字符串是“baba”,前缀是b,ba,bab;后缀是aba,ba,a。这里可以看出前后缀相等的最长的字符串是ba,长度是2,因此第四位的next值是2。
第五位,字符串是“babab”,前缀是b,ba,bab,baba;后缀是abab,bab,ab,b。这里可以看出前后缀相等的最长的字符串是bab,长度是3,因此第五位的next值是3。
-
数据结构-串-KMP算法详解(Next数组计算)(简单易懂)
2022-04-11 20:38:24数据结构kmp算法 next数组计算 如何使用next匹配
本文章就专讲kmp,暴力匹配就不讲了(我相信能搜索kmp的,暴力匹配算法应该也都了解过了)
为什么网上那么多讲kmp 我还发文章,很多文章我觉得讲的不是太通俗易懂,大多数我看起来都觉得有些懵逼KMP介绍
提示:以下信息来源百度
KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt提出的,因此人们称它为克努特—莫里斯—普拉特操作(简称KMP算法)。KMP算法的核心是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现,函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n)
上面讲了kmp需要求匹配字符串的next数组来快速匹配,那我们先来讲解一下如何求next数组
一、求Next数组
求Next数组前我们需要了解字符串的前缀表与后缀表
前后缀表
如字符串“ABCD”的前后缀表
了解完字符串前后缀,接下来我们要开始求最长公共前后缀
求最长公共前后缀
我们以“aabaac”为例
字符串中要没有公共的前后缀就为0
从以上方法就能求出字符串“aabaac”的最长公共前后缀数组为
[0,1,0,1,2,0]最长相等前后缀表转Next数组
当然变成Next数组前还需要进行简单的处理(其实也就把最长公共前后缀数组右移而已)
在最长公共前后缀前面加上 -1 并去掉最后一位就是next数组了
Next数组的第一位永远是-1,第二位永远是0注意:Next数组有很多种求法,依据匹配字符串的代码来做选择,我选择的方法next数组第一位是-1,还有另一种方法开头是0,但原理都是相同的所以不必纠结
二、使用Next数组来匹配字符串
为了能较好体现kmp算法:
主串:“aaacaacaaad”
模式串:“aaad”
模式串Next数组:[-1,0,1,2]在主串和匹配串字符相同的情况下,指针 i 和 j 后移
或者遇到主串和匹配串字符不相同时 但next值为-1时指针 i 和 j 后移
步骤一:
1i、1j、2i、2j代表指针位置及步骤,中间字符相等的地方我就不讲了,就主要讲重点的地方指针4i和4j的字符不相同,不匹配位置的next值为2(蓝色的a),所以需要将匹配串右移到匹配串索引2的位置
步骤二:
匹配串后移后指针i和j的字符依然还是不相同,不匹配位置的next值为1(蓝色的a),所以需要将匹配串右移到匹配串索引1的位置
步骤三:
匹配串后移后指针i和j的字符依然还是不相同,不匹配位置的next值为0(蓝色的a),所以需要将匹配串右移到匹配串索引0的位置
步骤四:
匹配串后移后指针i和j的字符依然还是不相同,但这时next值为-1,这就需要指针i和j向后移
步骤五:
指针i和j后移后,(中间字符相同的地方就不解说了),指针到3i和3j的字符不相同,next值为1,然后就和之前讲的步骤一样,需要将匹配串右移到匹配串索引1的位置
步骤六:
后面的步骤就不再多叙述,自己看图分析
步骤七:
步骤八:
然后这就匹配完成了
总结
代码后续会补充
非常感谢您能看到这,本人第一次写文章,所以我可能讲的不是很好,如有问题望大家能多多提醒,感谢。下次讲sunday算法
注:如看不懂,可以的话,麻烦您在评论区中发句看不懂,好让我知道我写的烂不烂
-
字符串next和nextval值的计算
2020-03-20 23:52:45字符串next和nextval值的计算 针对字符串ababaabab,计算next和nextval的值。 第一行是序号,从0开始。 第二行是字符串的元素 第三行是next值,为当前位置前面字符串收尾重复的最长字符个数。 第四行是...字符串next和nextval值的计算
针对字符串
ababaabab
,计算next
和nextval
的值。-
第一行是序号,从0开始。
-
第二行是字符串的元素
-
第三行是
next
值,为当前位置前面字符串收尾重复的最长字符个数。 -
第四行是
nextval
值,当以next
和以i
为索引的字符不相同时,nextval
值就是next
值。当两个字符相同时,nextval
值是以next
为索引的nextval
值。
next 值的计算
举个例子,当
i=5
时,计算方法如下:其中,0和1的
next
值固定为-1和0.nextval值的计算
0的
nextval
值固定为-1
。i 0 1 2 3 4 5 6 7 8 s a b a b a a b a b next -1 0 0 1 2 3 1 2 3 nextval -1 0 -1 0 -1 3 0 -1 0 有时候下标从1开始,则
nextval
就是010104101
. -
-
KMP算法中模式串移动next数组的计算
2020-10-21 20:36:49题目描述 字符串的子串定位称为模式...请参考教材next数组的计算公式与算法,编程实现之。 输入 一个模式串,仅由英文小写字母组成。长度不大于100。 输出 输出模式串对应的移动数组next。每个整数后跟一个空格。 样 -
(算法)通俗易懂的字符串匹配KMP算法及求next值算法
2018-10-06 00:23:54大多数据结构课本中,串涉及的内容即串的模式匹配,需要掌握的是朴素算法、KMP算法及next值的求法。在考研备考中,参考严奶奶的教材,我也是在关于求next值的算法中卡了一下午时间,感觉挺有意思的,把一些思考的... -
数据结构——串中kmp算法求模式串中next函数值
2021-11-05 15:45:433.第三位的next值:看第二位的模式串为b,对应的next值为1,则将第二位的模式串b与j=1的模式串进行比较,不同,则没有相同的字符串,值为1。 4.第四位的next值:看第三位的模式串为c,对应的next值为1,则将第三位的... -
KMP算法next数组计算--字符串方式
2017-06-19 23:51:17用字符串的方式说明模式串匹配中KMP算法求解next数组的方式 -
串——求解next数组和nextval数组
2021-05-23 01:52:25求解nextnext数组的求解方法:首先第一位的next值直接给0,第二位的next值直接给1,后面求解每一位的next值时,都要前一位进行比较。首先将前一位与其next值的对应位进行比较,若相等,则该位的next值就是前一位的... -
字符串匹配问题——next数组计算
2017-08-18 16:19:44在KMP算法中,最关键的就是求解next数组了。那么如何快速求解next数组呢? 已知模式串:A B C D A B D D A 其next数组:0 0 0 0 120 0 1 那么是如何求证出来的呢? 首先字符串从左至右遍历。 第一个字符A的next... -
模式串的next()函数值
2020-05-27 17:44:37模式串:ababaaaba next:011234223 方法: 前两位是0和1 第三位:前一位b对应的next值为1,1对应的a(在数组中第一个数为a)和b不相同,故第三位的next值为1 第四位:前一位a对应的next值为1,1对应的a和a相同,故... -
C++ 数据结构之kmp算法中的求Next()函数的算法
2020-08-30 03:47:23主要介绍了C++ 数据结构之kmp算法中的求Next()函数的算法的相关资料,需要的朋友可以参考下 -
kmp算法计算模式串的next值
2016-11-18 19:22:27此时意味着主串和子串的下标都需要加1; //2、val={0,1...k-1}中的任意值,k为正在比较的第k个字符,也就是说当他们不相等时,需要回溯到val继续比较; void get_next(char *p,int n) { int i=0,k; k=next[0]=-1;/... -
字符串之KMP算法求解next数组(C语言)
2021-06-13 15:10:56next数组的作⽤:当模式串的第j个字符失配时,从模式串的第next[j]的继续往后匹配。 ①、任何模式串都一样,第一个字符不匹配时,只能匹配下一个子串,<font color='red'>next[1]都无脑写0 ②、任何模式串都一样,第... -
计软: KMP算法的next函数怎么计算
2021-08-18 14:49:49计软刷题时刷到一个题目,模式串p为“abaac”,求其next函数。代码就不解析了(我也没咋看),为了应试总结了一个快速答题技巧。 首先,按位序、模式串、next函数写下来: 位序 1 2 3 4 5 模式... -
字符串next函数求值
2017-10-11 21:31:26先看看next数据值的求解方法 位序 1 2 3 4 5 6 7 8 9 模式串 a b a a b c a b c next值 0 1 1 2 2 3 1 2 3 next数组的求解方法是: 1.第一位的next值为0 2.第二位 -
数据结构字符串模式匹配中计算next和nextval的值(C语言)
2019-10-26 11:10:23其实计算next的值本身也就是对模式串进行模式匹配,我们一起看看计算next的值的过程; 当模式串 P=“ababcabaababb” 时计算它的next值。 比如: 代码: void get_next(m_1 A) { int i=-1,j=0; A-&... -
求字符串的next值的两种方法
2019-03-01 22:06:04自己目前掌握的有两种求字符串next值的方法,下面用简单通俗的描述记录下来。 以字符串ababaaababaa(下文也称为字符串s)为例,其next值为011234223456,下面介绍两种求解方法,其中无论是字符串s或是next数组,下标... -
KMP算法初始化模式串的next数组
2020-05-14 17:03:52在使用KMP算法处理字符串查找问题的过程当中,可以利用模式串本身的对称性,在移动模式串的时候,尽量多的往后移动,减少无用的查找过程,而模式串本身的对称性一般是保存在一个next数组里面的,下面来讨论下怎么... -
字符串匹配KMP算法的理解及求next值(简单介绍)
2021-04-20 15:39:49例如:现在有一个文本串S=“BBC ABCDAB ABCDABCDABDE”和一个搜索串(模式串)p="ABCDABD",要查找p在s中的位置。(暴力算法的代码就不贴了,此算法的时间复杂度最好为O(n+m)、最坏为O(nm)) 这样只能一个一个的去... -
串的模式匹配——KMP中next函数的计算
2018-08-30 16:59:52KMP算法相比于朴素的模式匹配算法,其改进之处在于:利用已经得到的“部分匹配”结果将模式串向右“滑动”尽可能远的距离。...我们介绍两种方法来计算模式串的next函数 方法一:传统方法 方法二:简便方法... -
KMP 算法以及 next 数组计算
2018-08-23 17:01:26看本文的同志们需要注意的是,本文没有按照一般的套路来介绍KMP算法,而是侧重于介绍KMP算法为什么这样做,关于KMP算法和next非常值得一看的博客推荐如下: https://www.cnblogs.com/tangzhengyue/p/4315393.html ... -
数据结构复习5:KMP算法next数组计算方法
2021-10-05 18:23:19串的模式匹配KMP算法中next[]数组的求解总结 步骤(1) 初始化 next[1]=0 next[2]=1; 步骤(2) 求next[j],令k=next[j-1] 步骤(3) S[j-1] S[k] 比较大小 = , next[j]=... -
KMP快速计算next与nextval
2019-06-10 09:54:41最近在研究数据结构,碰到了计算next与nextval值,查看了大量资料,发现这个方法最是清楚明白,整理后贡献出来,有问题可以留言哟! 方法1:引入了一个maxL,在计算nextval时,比较方便。强烈建议读者按照思路算一遍,... -
串′ababaaababaa′的next数组(求next数组思路与实例)
2018-06-17 16:53:46首先在将例子之前先说说这个next数组求解的思路:第一位的next的值是0,第二位的next的值为1,后面求解每一位的next的值时。首先将前一位与其next值对应的内容进行比较,如果相等,则该位的next值就是前一位的next值... -
计算next和nextVal值
2020-04-09 16:58:19计算时只用到子串,也就是模式串(这里用到一个maxL值) 这里模式串为:abaabcac 第一步将模式串写上序号,我们这里从1开始(有的从0开始,建议充1开始) 然后计算出maxL值,列出从第一个开始的子串,找出相等的... -
理解next数组的计算方式
2019-01-21 20:52:30i 0 1 2 3 4 5 6 7 8 9 10 11 s a b a b a a a b a b a a next[i] -1 0 0 1 2 3 1 1 2 3 4 5 先计算前缀next[i]的值:... -
Next 值与 Nextval 值的计算
2018-05-20 20:42:05KMP算法对模式串求解其Next值和Nextval值的计算方法 Next值的计算 方法一 方法二 Nextval值的计算 模式串S = “abaabcac” ,求其 Next 数值序列: 1 2 3 4 5 6 7 8 a b a a b... -
KMP算法中计算next数组的代码
2020-11-04 17:24:55如:严蔚敏《数据结构》将模式串下标从1开始计数,故定义next[1]=0,next[2]=1。李春葆《数据结构》将模式串下标从0开始计数,故定义next[0]=-1,next[1]=0。但这两种定义方式,不影响它们有一致的计算方法,即“若... -
KMP算法之Next数组如何计算
2019-10-24 14:41:01哈哈哈KMP算法之Next算法之如何计算简的描述抛出疑问所以看懂下面的图最简单的实现 KMP算法之Next算法之如何计算 简的描述 K,J为两个“指针”,K指向前缀,J指向后缀。 当P[K]==P[J],则 K++,J++,匹配下一个...