精华内容
下载资源
问答
  • 提到子串的模式匹配算法就不得不提到大名鼎鼎的KMP算法,而KMP算法的实现离不开next数组,今天我们就来说一下有关next数组的问题。  首先我们列出next的函数定义:  0,当j=1时 next[j]= Max{k|1  1 其他情况 ...

           提到子串的模式匹配算法就不得不提到大名鼎鼎的KMP算法,而KMP算法的实现离不开next数组或nextval数组,今天我们就来说一下有关next数组和nextval数组求值的问题。

    我们先来看下next数组

       首先我们列出next的函数定义:

              0,当j=1时

    next[j]=  Max{k|1<k<j,且’p1…pk-1’=’pj-k+1…pj-1’}当此集合不为空时

              1 其他情况

    对于这个函数什么意思我们通过具体的例子来理解

    T=”ababcb”

                j 123456

    模式串T ababcb

       next[j] 011231

    1)   当j=1时 next[1]=0;

    2)   当j=2时  由1到j-1只有一个字符“a”,属于其他情况next[2]=1;

    3)   当j=3时  1到j-1是串“ab”,显然“a”与“b”不相等,属其他情况,next[3]=1;

    4)   当j=4时  1到j-1是串“aba”,此时前缀字符“a”与后缀字符“a”相等,由此可推算k值等于2(由’p1…pk-1’=’pj-k+1…pj-1’,得到p1=p3),next[4]=2;

    5)   当j=5时  1到j-1是串“abab”,此时前缀字符“ab”与后缀字符“ab”相等,k值为前缀字符与后缀字符相等的个数加1,next[5]=3;

    6)   当j=6时 1到j-1是串“ababc”,由于前缀字符“a”与后缀字符“c”并不相等,所以属于其他情况,next[6]=1;


           我们根据经验可以得到如果前后缀一个字符相等,next[j]值是2,2个字符相等next[j]值是3,n个字符相等next[j]值就是n+1。

           还有一种情况要特别注意一下如串“ababac”,当j=6时,由于“aba”与“aba”相等,重叠了一个“a”,此时next[6]=4;

         

           讲完next数组之后,我们再来讲一下nextval数组,我们看下面的例子:

    T=”ababaaaba”

                      j 123456

          模式串T ababaa

              next[j] 011234

          nextval[j] 010104

    先算出next数组的值分别为011234,然后再分别判断

    1)        当j=1时,nextval[1]=0,这没什么好说的

    2)        当j=2时,因为第二位字符“b”的next值为1,所以我们去与第一位字符“a”比较,它们不相等,则nextval[2]=next[2]=1;

    3)        当j=3时,第三位字符“a”与第next[3]位(即第一位)字符 “a”相等,所以nextval[3]=nextval[1]=0;

    4)        当j=4时,第四位字符“b”与第next[4]位(即第二位)字符 “b”相等,所以nextval[4]=nextval[2]=1;

    5)        当j=5时,第五位字符“a”与第next[5]位(即第三位)字符 “a”相等,所以此时nextval[5]=nextval[3]=0;

    6)        当j=6时,第六位字符“a”与第next[6]位(即第四位)字符“b”不相等,此时nextval[6]=next[6]=4;

    根据以上例子相信你们也能发现规律如下:

    nextval[1]永远等于0,之后的第j位字符先去与第next[j]位字符比较,如果相等nextval[j]=nextval[n](n=next[j]),若不相等则nextval[j]=next[j]

       以上就是博主关于next数组和nextval数组求值的一些看法,有什么问题欢迎指正。

    以上内容参考自《大话数据结构》


    展开全文
  • 如何利用KMP算法快速求解next数组和nextval数组

    如何利用KMP算法快速求解next数组和nextval数组

    其实求next数组和nextval数组一直是一个让人头疼的问题,具体来看,有两种情况:

    1.字符串编号从0开始编号
    2.字符串编号从1开始编号

    但是我们平时试卷上的参考答案一般都是从1开始编号。下面我们从一个简单的例子来开始对next数组和nextval数组的认识
    模式串S: abaabcac

    S12345678
    模式串Stringabaabcac
    next数组01122312
    nextval数组01021302
    首先我们来分析next数组
    一般来说next数组的第一位为0,第二位为1,第三位的时候我们就观察模式串的前两位,发现是a和b,
    这时我们就要做最长前缀后缀匹配,算出最大的公共元素长度,然后加1就是这一位的next值,比如这道题里面,
    第三位a的前两位是a和b,最大公共元素长度为0,所以该位的next值是1,依次类推可以得到后面的next值,
    这里就不再赘述
    
    接下来我们就要求nextval数组的值了,原理如下:求nextval[i]的值,我们要比较String[i]和String[next[i]]的值
    如果String[i]和String[next[i]]的字符相等,那么nextval[i]的值就等于nextval[next[i]]的值,
    如果String[i]和String[next[i]]的字符不相等,那么nextval[i]的值就等于next[i]的值。
    

    上面毕竟都是理论上的东西,我们就上面的例子来说明一下:比如我们要求nextval[3]的值,我们就要比较
    S[1]和S[3]的字符,我们发现他们都是a,相等,所以nextval[3]就等于nextval[0]的值,也就是0.
    那么nextval[4]的值怎么求呢? 同理,我们比较S[2]和S[4]的字符,发现一个是b,一个是a,他们不相等。
    所以nextval[4]的值就等于next[4]的值,也就是2啦!
    不知道你们学会了没有???
    上面那道例题是2016年北邮803的真题啦!

    回到我们最开始提出的两种情况,还有一种情况是以0开始编号的S数组,这种情况我们怎么办呢?其实我们可以先把以1开始的S数组的next数组和nextval数组求出来,然后全体减1就可以得到另外一种情况的nextval数组!

    距离2020考研还剩29天!!!加油!!!!

    展开全文
  • KMP算法中,如何手动求next数组和nextval数组? 首先我们要理解next数组的意义,为了实现更加高效的字符匹配,next数组是用来寻找字符串数组内部的自身的一种规律,利用字符串内部的一种相似性,来优化字符串数组...

    KMP算法中,如何手动求next数组和nextval数组?

    首先我们要理解next数组的意义,为了实现更加高效的字符匹配,next数组是用来寻找字符串数组内部的自身的一种规律,利用字符串内部的一种相似性,来优化字符串数组匹配算法。所以才需要计算这么一个next数组来帮助算法更好的实现字符串匹配。

    next数组的计算方式逻辑上稍微复杂,初学者可能很难看懂,所以首先要理解,为什么要计算next数组以及更加优化的nextval数组。

    假如有这样一串字符串

    1 2 3 4 5 6

    a a a a a a

    这可以说是一个字符串间规律最强的一个数组了吧,让我们来手动模拟一下。

    首先默认第一位是0,第二位是1,从第3位开始求,比较第3-1位和next[3-1]的字符是否相同,若相同,则next[3]=next[2]+1

    所以第3位的值就是2.那么依此类推就可以得到,这个字符串的next数组为

    1 2 3 4 5 6

    a a a a a a

    0 1 2 3 4 5

    总结来看就是相同就在他的next数组值加1.

    那么有这样一个字符串那

    1 2 3 4 5 6

    a b c d e f

    默认给出第1位为0 第二位为1 ,发现全都不一样,可以说毫无相关性了,所以next数组为

    1 2 3 4 5 6

    a b c d e f

    0 1 1 1 1 1

    这两种极端情况可以让大家初步了解一下计算next数组的方法,起码可以初步理解一下next数组的意义。但是这还不完善。

    下面介绍一到北邮2016年考研真题

    1 2 3 4 5 6 7 8

    a b a a b c a c

    0 1 1 2 2 3 1 2

    这是一个考试常见的字符串,是如何计算的那?

    第n位:next[n]的值来自于第n-1位的字符,通过跟第next[n-1]位字符比较,如果相同next[n]=next[n-1],如果不相同,就跟第next[next[n-1]]位的字符比较,就这样迭代直到相同的时候,加上1,如果实在没有,就为1.

    这一段话可能很难理解,逐位分析。

    让我们从依次来看:

    第3位:第2位和第1位比较,不相同 所以为1

    第4位:第3位和第1位比较,相同,所以为2

    第5位:第4位和第2位比较,不相同,和第1位比较,相同,所以为2

    第6位:第5位和第2位比较, 相同,所以为3

    第7位:第6位和第3位比较,不同,和第1位比较,不同,所以为1

    第8位:第7位和第1位比较,相同,所以为2.

    这就是next数组的手动计算方法。

    接下来介绍如何根据next数组计算nextval数组

    nextval是在next数组的基础上优化算法,避免不必要的浪费。其实我也不太理解nextval的具体原理,现只能介绍一下如何计算。

    依旧用上面北邮的真题为例,其真题本身求的就是nextval数组

    现在我们已经有了next数组:

    1 2 3 4 5 6 7 8

    a b a a b c a c

    0 1 1 2 2 3 1 2

    现在通过next数组计算nextval数组,nextval数组与next相反,是找不同,

    1 2 3 4 5 6 7 8

    a b a a b c a c

    0 1 1 2 2 3 1 2

    0 1 0 2 1 3 0 2

    第1位:必为0

    第2位:第2位next值为1,所以第2位和第1位比较,不同,为第2位的next 值1

    第3位:第3位next值为1,所以第3位和第1位比较,相同,因为到第1位了,所以为0

    第4位:第4位next值为2,所以第4位和第2位比较,不同,就为第4位next值2

    第5位:第5位next值为2,所以第5位和第2位比较,相同,则继续,第2位和第1位不同,则为第2位的next值1

    第6位:第6位next值为3,所以第6位和第3位比较,不同,就为第6位的next值3

    第7位:第7位next值为1,所以第7位和第1位比较,相同,则为0

    第8位:第8位next值为2,所以第8位和第2位比较,不同,则为第8位的next值2

    【简而言之】第n位nextval数组值就是,让第n位字符和第next[n]位比较,不同,则nextval[n]=next[n],如果相同,则比较第next[next[n]]位和第next[n]位比较,如果不同,则nextVal[n]=next[next[n]].就是这样的计算方式。

     

     

    展开全文
  • 书上求next数组和nextval数组的代码如下: 快速求next数组的方法: i == 1时,next[1]的为0 i >=2 时,next[i]的为字符串 [1,…,i-1]的最大公共前后缀的长度再加1 前缀不包括最后那个字符,后缀不包括第...

    这篇博客发出来只是为了应付明天的数据结构考试,如有错误欢迎指正!

    《数据结构C语言版第2版》的课后习题里有这两道题(答案是CA)
    在这里插入图片描述
    书上求next数组和nextval数组的代码如下:
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    快速求next数组的方法:

    1. i == 1时,next[1]的值为0
    2. i >=2 时,next[i]的值为字符串 [1,…,i-1]的最大公共前后缀的长度再加1
      前缀不包括最后那个字符,后缀不包括第一个字符,比如aaaaa的公共前后缀是aaaa,而不是aaaaa

    计算ababaaababaa的next数组:
    next[1] = 0
    next[2]:子串[1,1]的子串是a,最大公共前后缀为0,所以next[2] = 0+1 = 1
    next[3]:子串[1,2]的子串是ab,最大公共前后缀为0,所以next[3] = 0+1 = 1
    next[4]:子串[1,3]的子串是aba,最大公共前后缀为1,所以next[4] = 1+1 = 2
    next[5]:子串[1,4]的子串是abab,最大公共前后缀为2,所以next[5] = 2+1 = 3
    next[6]:子串[1,5]的子串是ababa,最大公共前后缀为3,所以next[6] = 3+1 = 4
    next[7]:子串[1,6]的子串是ababaa,最大公共前后缀为1,所以next[7] = 1+1 = 2
    next[8]:子串[1,7]的子串是ababaaa,最大公共前后缀为1,所以next[8] = 1+1 = 2
    next[9]:子串[1,8]的子串是ababaaab,最大公共前后缀为2,所以next[9] = 2+1 = 3
    next[10]:子串[1,9]的子串是ababaaaba,最大公共前后缀为3,所以next[10] = 3+1 = 4
    next[11]:子串[1,10]的子串是ababaaabab,最大公共前后缀为4,所以next[11] = 4+1 = 5
    next[12]:子串[1,11]的子串是ababaaababa,最大公共前后缀为5,所以next[12] = 5+1 = 6
    (不需要求next[13])
    所以这个next数组就求完了,答案为[0,1,1,2,3,4,2,2,3,4,5,6]

    快速求nextval数组的方法:

    1. 先求出next数组
    2. 先拷贝next数组的所有值到nextval
    3. 假设字符串是s,长度为n,从1到n逐一扫描nextval数组
    4. 如果s[nextval[i]] == s[i],那么把nextval[i]的值改成nextval[nextval[i]]的值,否则就保持不变。

    就写到这了,睡觉!

    展开全文
  • 首先在将例子之前先说说这个next数组求解的思路:第一位的next的是0,第二位的next的为1,后面求解每一位的next的时。首先将前一位与其next对应的内容进行比较,如果相等,则该位的next就是前一位的next...
  • 继上一篇关于模式匹配算法的博文,我想在这里在继续详细解说一下next数组和nextval数组值的推导。 文章目录为什么需要next数组 为什么需要next数组 next数组到底是用于什么的?为什么要有next数组? 在这里我们...
  • next数组

    2017-09-11 12:26:12
    已知串S=′aaab′,其Next数组值为() 正确答案: A 0123 1123 1231 1211 next数组的求解方法是:第一位的next值为0,第二位的next值为1,后面求解每一位的next值时,根据前一位进行比较。首先将前一位与其next...
  • KMP算法求next数组和nextval数组方法总结 首先next数组,以下是天勤给出的求解步骤 FL为从左边第一个字符起的字串 FR为从右边第一个字符起的字串 如果没理解可以看下面的例子 例如模式串为 1 ...
  • KMP算法手工求next数组和nextval数组 复习到kmp算法,查了些资料,在此记录一个相对简单的求nextnextval的方法 1.求next数组 当i&amp;amp;lt;2时: next[1]=0 next[2]=1 当i&amp;amp;gt;2时: ...
  • 最简单的求next 数组和 nextval数组的方法

    千次阅读 多人点赞 2018-11-29 16:13:25
    求 nextval: 第 i 个字符 (i 的下标从 1开始)若与 第next[i] 上的字符不同,nextval[i]保持为 next[i] ,否则 更新为 第next[i]上的nextval(也就是 nextval[next[i]])。(不同保持不变,相同则替换) 下标 ...
  • 算法:next数组的求法详解

    万次阅读 多人点赞 2019-01-27 16:26:48
    我们能确定next数组第一二位一定分别为0,1,后面求解每一位的next时,根据前一位进行比较。 从第三位开始,将前一位与其next对应的内容进行比较, 如果相等,则该位的next就是前一位的next加上1; 如果...
  • next数组介绍

    千次阅读 2015-09-13 20:49:48
    首先看看next数组值的求解方法例如:  模式串 a b a a b c a c  next值 0 1 1 2 2 3 1 2     next数组的求解方法是:第一位的next值为0,第二位的next值为1,后面求解每一位的next值时,根据前一位进行比较。...
  • KMP 算法我们有写好的函数帮我们计算 Next 数组值和 Nextval 数组的值,但是如果是考试,那就只能自己来手算这两个数组了,这里分享一下我的计算方法吧。 计算前缀 Next[i] 的值: 我们令 next[0] = -1 。从 next...
  • next数组
  • KMP入门级别算法详解--终于解决了(next数组详解)

    万次阅读 多人点赞 2017-08-16 22:55:36
    对于正常的字符串模式匹配,主串长度为m,子串为n,时间复杂度会...KMP算法用到了next数组,然后利用next数组来提高匹配速度,我首先讲一下next数组怎么求,之后再讲匹配方式。 next数组详解 首先是理解KMP...
  • 当 j=1,2 时,其 next 数组固定为 0,1 当 j>2 时,比较从模式串(匹配串)T 的第 1 位到 j-1 位的数字相同情况。若有 n 个相同,则 next为 n+1 PS:其中匹配的时候,前后缀不能完全匹配。 2. nextval ...
  • 求KMP算法的next数组 今天刷到一个笔试题,求一个字符串在KMP算法下的next数组 几番百度看题解,居然大多数的题解都有毛病被一顿吐槽 最后,通过一张动图搞懂了计算的原理 如下: 本图来自这个博客 正如下面评论...
  • KMP 算法我们有写好的函数帮我们计算 Next 数组值和 Nextval 数组的值,但是如果是考试,那就只能自己来手算这两个数组了,这里分享一下我的计算方法吧。 计算前缀 Next[i] 的值: 我们令 next[0] = -1 。从 next...
  • kmp求next数组值的方法

    千次阅读 2010-10-03 09:28:00
    首先看看next数组值的求解方法。 例如: 模式串abaabcac next值01122312 nextval值 next数组的求解方法是:第一位的next值为0,第二位的next值为1,后面求解每一位的next值时,根据前一位进行比较。首先将前一位...
  • next数组的求解方法是:第一位的next为0,第二位的next为1。后面求解每一位的next时,根据前一位进行比较。首先将前一位与其next对应的内容进行比较,如果相等,则该位的next就是前一位的next加上1;...
  • 当时对我帮助大大的~~~原文地址:KMP算法求next数组和nextval数组的简单方法作者:小二晨Ellennext数组的求解方法是:第一位的next为0,第二位的next为1。后面求解每一位的next时,根据前一位进行比较。首先将...
  • KMP算法 next数组 nextval数组

    千次阅读 2020-02-20 20:55:49
    文章目录KMP算法简介KMP算法过程next数组的定义及实现next数组实现代码next数组的改进KMP算法的代码实现 KMP算法简介 KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.MorrisV.R.Pratt提出的,因此人们称它...
  • next数组两种求法

    万次阅读 多人点赞 2018-08-22 15:03:37
    (1)看到网上同一个字符串求 next 数组的有两种,一种是 -1 开头,一种是 0 开头,虽然有差别,但是以 0 开头的next数组的每一项都比以 -1 开头的next数组的对应项大1,所以,具体是以 0 开头还是以 -1 开头看...
  • next数组的求解方法是:第一位的next为0,第二位的next为1,后面求解每一位的next时,根据前一位进行比较。首先将前一位与其next对应的内容进行比较,如果相等,则该位的next就是前一位的next加上1;...
  • Next数组个人理解

    2018-01-19 21:16:08
    1.“Next数组”中第i位表示在与母串发生失配时应该跳转到的用来比较的那一位; 2.“Next数组”中第i位可以表示以第i-1位为结尾的后缀串的长度;  引申:最后一位的下一位的可以表示最后一位为结尾的后缀串是否...
  • next数组求解详解

    万次阅读 多人点赞 2017-08-20 20:52:59
    next数组求解详解,以串'ababaaababaa'为例
  • KMP算法next数组详解

    千次阅读 2017-02-02 17:48:09
    这里的已匹配信息叫做部分匹配表,也叫做next数组。其存储的是字符串的前缀后缀重合部分的字符数。以此来控制模式串的移动位数。next数组生成的步骤: 假设模式串是“ABABABB” 前缀:除最后一个字符外,例如,A、...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 542,870
精华内容 217,148
关键字:

next数组和next数组值