精华内容
下载资源
问答
  • 首先在将例子之前先说说这个next数组求解的思路:第一位的next的值是0,第二位的next的值为1,后面求解每一位的next的值时。首先将前一位与其next值对应的内容进行比较,如果相等,则该位的next值就是前一位的next值...

    刚刚开始遇到这个问题说实话完全懵逼,然后简单搜了下,还是理解的模棱两可。最后看了几篇博客,现在才算是真正的理解了。

    首先在将例子之前先说说这个next数组求解的思路:

    第一位的next的值是0,第二位的next的值为1,后面求解每一位的next的值时。首先将前一位与其next值对应的内容进行比较,如果相等,则该位的next值就是前一位的next值加上1;如果不等,如果不等,向前继续寻找next值对应的内容与前一位进行比较(向前继续寻找next值对应的内容与next值对应的内容的next前一位进行比较),直到找到某个位上的内容的next值对应的内容与前一位相等为止,则这个位对应的值加上1即为需求的next值;如果找到第一位都没有找到与前一位相等的内容,那么需求的位上的next值即为1。所以中心思想则是递进查看前一位的next对应的是否和前一位相同。找到相同的则在找到的基础上加1。

    求串′ababaaababaa′的next数组

    模式串ababaaababaa
    下标123456789101112

    1、前两位:next数组前两位规定是0,1 即前两位ab对应的next数组为01,则:

    模式串ababaaababaa
    下标123456789101112
    next数组01          

    2、接下来看第三位,按照next数组求解方法。第三位a的前一位为第二位的b,b的next值为1对应内容为a,b与a不同,向前继续寻找next值对应的内容来与前一位进行比较。因为找到第一位都没有找到与前一位相等的内容,所以第三位a的next值为1,则:

    模式串ababaaababaa
    下标123456789101112
    next数组011         

    3、接下来看第四位b,b的前一位a的next值1对应内容为a,相同,所以该位b的next值就是前一位a的next值加上1,即为2

    模式串ababaaababaa
    下标123456789101112
    next数组0112        

    4、接下来看第五位a,a的前一位b的next值2对应内容为b,相等,所以该位a的next值就是前一位b的next值加上1,即为3

    模式串ababaaababaa
    下标123456789101112
    next数组01123       

    5、接下来看第六位a,a的前一位a的next值3对应内容为a,相等,所以该位a的next值就是前一位a的next值加上1,即为4

    模式串ababaaababaa
    下标123456789101112
    next数组011234      

    6、接下来看第七位a,a的前一位a的next值4对应内容为b,不相等,向前继续寻找next值对应的内容来与前一位进行比较,b的next值2对应的内容为b,依旧不相等,继续向前寻找,第二位b的next值1对应内容为a,相等。因为是在第二位b处实现的相等,所以第七位a的next值为第二位b的next值上加1,即为2

    模式串ababaaababaa
    下标123456789101112
    next数组0112342     

    7、接下来看第八位,同样道理,得出b的next值为2

    模式串ababaaababaa
    下标123456789101112
    next数组01123422    

    8、接下来看第九位,前一位b的next值2对应内容为b,相等,所以此处next值为3

    模式串ababaaababaa
    下标123456789101112
    next数组011234223   

    9、第十位同理可得,为4

    模式串ababaaababaa
    下标123456789101112
    next数组0112342234  

    10、第十一位a的前一位b的next值4对应内容为b,相等,所以此处next值为5

    模式串ababaaababaa
    下标123456789101112
    next数组01123422345 

    11、最后,第十二位同理可以得到next值位6

    模式串ababaaababaa
    下标123456789101112
    next数组011234223456

    展开全文
  • 这篇博客发出来只是为了应付明天的数据结构考试,如有错误欢迎指正! 《数据结构C语言版第2版》的课后习题里有这两道题(答案是CA) 书上求next数组和nextval数组的代码如下: ...计算ababaaababaa的next数组: ne

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

    《数据结构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]]的值,否则就保持不变。

    就写到这了,睡觉!

    展开全文
  • 假设求串′ababaaababaa′的next数组 模式串ababaaababaa 下标 1 2 3 4 5 6 7 8 9 10 11 12 1、前两位:next数组前两位一定是0,1 即前两位ab对应的next数组为01,则: 模式...

    假设求串′ababaaababaa′的next数组

    模式串ababaaababaa
    下标 1 2 3 4 5 6 7 8 9 10 11 12

    1、前两位:next数组前两位一定是0,1 即前两位ab对应的next数组为01,则:

    模式串ababaaababaa
    下标 1 2 3 4 5 6 7 8 9 10 11 12
    next数组 0 1                    

    2、接下来看第三位,按照next数组求解方法。第三位a的前一位为第二位的b,b的next值为1对应内容为a,b与a不同,向前继续寻找next值对应的内容来与前一位进行比较。因为找到第一位都没有找到与前一位相等的内容,所以第三位a的next值为1,则:

    模式串ababaaababaa
    下标 1 2 3 4 5 6 7 8 9 10 11 12
    next数组 0 1 1                  

    3、接下来看第四位b,b的前一位a的next值1对应内容为a,相同,所以该位b的next值就是前一位a的next值加上1,即为2

    模式串ababaaababaa
    下标 1 2 3 4 5 6 7 8 9 10 11 12
    next数组 0 1 1 2                

    4、接下来看第五位a,a的前一位b的next值2对应内容为b,相等,所以该位a的next值就是前一位b的next值加上1,即为3

    模式串ababaaababaa
    下标 1 2 3 4 5 6 7 8 9 10 11 12
    next数组 0 1 1 2 3              

    5、接下来看第六位a,a的前一位a的next值3对应内容为a,相等,所以该位a的next值就是前一位a的next值加上1,即为4

    模式串ababaaababaa
    下标 1 2 3 4 5 6 7 8 9 10 11 12
    next数组 0 1 1 2 3 4            

    6、接下来看第七位a,a的前一位a的next值4对应内容为b,不相等,向前继续寻找next值对应的内容来与前一位进行比较,b的next值2对应的内容为b,依旧不相等,继续向前寻找,第二位b的next值1对应内容为a,相等。因为是在第二位b处实现的相等,所以第七位a的next值为第二位b的next值上加1,即为2

    模式串ababaaababaa
    下标 1 2 3 4 5 6 7 8 9 10 11 12
    next数组 0 1 1 2 3 4 2          

    7、接下来看第八位,同样道理,得出b的next值为2

    模式串ababaaababaa
    下标 1 2 3 4 5 6 7 8 9 10 11 12
    next数组 0 1 1 2 3 4 2 2        

    8、接下来看第九位,前一位b的next值2对应内容为b,相等,所以此处next值为3

    模式串ababaaababaa
    下标 1 2 3 4 5 6 7 8 9 10 11 12
    next数组 0 1 1 2 3 4 2 2 3      

    9、第十位同理可得,为4

    模式串ababaaababaa
    下标 1 2 3 4 5 6 7 8 9 10 11 12
    next数组 0 1 1 2 3 4 2 2 3 4    

    10、第十一位a的前一位b的next值4对应内容为b,相等,所以此处next值为5

    模式串ababaaababaa
    下标 1 2 3 4 5 6 7 8 9 10 11 12
    next数组 0 1 1 2 3 4 2 2 3 4 5  

    11、最后,第十二位同理可以得到next值位6

    模式串ababaaababaa
    下标 1 2 3 4 5 6 7 8 9 10 11 12
    next数组 0 1 1 2 3 4 2 2 3 4 5 6

    综上,串′ababaaababaa′的next数组为011234223456

    转载于:https://www.cnblogs.com/lanqingzhou/p/8267879.html

    展开全文
  • next数组

    2017-05-19 11:18:58
    ababaaababaa的next数组为() 012345678999 012121111212 011234223456 0123012322345 答案是:C next的基本思想是:找这个字符的前一个字符,他的next值对应的内容比较,如果相等,则next...
    串′ababaaababaa′的next数组为()
    
    • 012345678999
    • 012121111212
    • 011234223456
    • 0123012322345 答案是:C

    next的基本思想是:找这个字符的前一个字符,他的next值对应的内容比较,如果相等,则next值加一,如果不相等,一直往前找,直到找到相等的为止。如果找到第一个字符仍然没有找到相等的,那这个字符的next的值则为1。

    下面是上题的解题步骤:
    a b a b a a a b a b a a
    0 1 1 2 3 4 2 2 3 4 5 6
    (1)next[1] = 0; next[2] = 1; (这两个是规定的)
    (2)接下来的字符:a 它前一个字符是:b 所对应的next:1 第一个字符:a,与b不相等,不能再往前
    所以a的next = 1;
    (3)接下来的字符:b 它前一个字符:a 所对应的next:1 第一个字符:a,与a相等
    所以b的next = 1+1 = 2;
    (4)接下来的字符:a 它前一个字符:b 所对应的next:2 第二个字符:b,与b相等
    所以a的next = 2+1 = 3;
    (5)接下来的字符:a 它前一个字符:a 所对应的next:3 第三个字符:a,与a相等
    所以a的next = 3+1 = 4;
    (6)接下来的字符:a 它前一个字符:a 所对应的next:4 第四个字符:b,与a不相等
    往前(从现在找的第四个字符b开始往前) 现找到的字符:b 所对应的next:2
    第二个字符:b,与a不相等,继续往前(从现在找的第二个字符b开始往前)
    现找到的字符:b 所对应的next:1 第一个字符:a,与a相等
    所以a的next = 1+1 = 2;
    (7)接下来的字符:b 它前一个字符:a 所对应的next:2 第二个字符:b,与a不相等
    往前(从现在找的第二个字符b开始往前) 现找到的字符:b 所对应的next:1
    第一个字符:a,与a相等 所以b的next = 1+1 = 2;
    (8)接下来的字符:a 它前一个字符:b 所对应的next:2 第二个字符:b,与b相等
    所以a的next = 2+1 = 3;
    (9)接下来的字符:b 它前一个字符:a 所对应的next:3 第三个字符:a,与a相等
    所以b的next = 3+1 = 4;
    (10)接下来的字符:a 它前一个字符:b 所对应的next:4 第四个字符:b,与b相等
    所以a的next = 4+1 = 5;
    (11)接下来的字符:a 它前一个字符:a 所对应的next:5 第五个字符:a,与a相等
    所以a的next = 5+1 = 6;
    展开全文
  • KMP入门级别算法详解--终于解决了(next数组详解)

    万次阅读 多人点赞 2017-08-16 22:55:36
    对于正常字符模式匹配,主长度为m,子串为n,时间复杂度会...KMP算法用到了next数组,然后利用next数组的值来提高匹配速度,我首先讲一下next数组怎么求,之后再讲匹配方式。 next数组详解 首先是理解KMP...
  • KMP算法理解之next数组

    2018-09-20 15:03:10
    .next数组的求法(这个是真有点困难。。。还好自己又搞明白了) 下面以字符串ababaaababaa为例说明一下 next[i](i从1开始算)代表着,除去第i个数,在一个字符串里面从第一个数到第(i-1)字符串前缀与后缀...
  • 再回到next[i]定义,对于ptr = "ababaaababaa";next[0] = -1,代表着除了第一个元素,之前前缀后缀最长重复子,这里是空 ,即"",没有,我们记为-1,代表空。(0代表1位...
  • 对于正常字符模式匹配,主长度为m,子串为n,时间复杂度会到达O(m*n),而如果用KMP算法,复杂度将会减少线型时间O(m+n)。 设主为ptr="ababaaababaa";...KMP算法用到了next数组,然...
  • 求字符串的next值的两种方法

    千次阅读 多人点赞 2019-03-01 22:06:04
    这两天在研究关于字符串匹配KMP算法,其中需要求...以字符串ababaaababaa(下文也称为字符串s)为例,其next值为011234223456,下面介绍两种求解方法,其中无论是字符串s或是next数组,下标均从1开始(注意不是0),...
  • 视频参考 对于正常字符模式匹配,主长度为m,子串为n,时间复杂度会...KMP算法用到了next数组,然后利用next数组的值来提高匹配速度,我首先讲一下next数组怎么求,之后再讲匹配方式。 next数组详解 ...
  • 判断题 KMP算法的特点是在模式匹配时指示主的指针不会变小回溯...ababaaababaa的next数组为: A. 012345678999 B. 012121111212 C. 011234223456 D. 0123012322345 字符‘ababaabab’ 的nextval 为
  • 与模式匹配

    千次阅读 2017-12-24 01:34:45
    解析 : 请参考 点击打开链接 2-1 (neuDS)设主的长度为n,模式的长度为m,则匹配的KMP算法时间复杂度是( )。...ababaaababaa的next数组为: (2分) 012345678999012
  • 对于正常字符模式匹配,主长度为m,子串为n,时间复杂度会到达O(m*...KMP算法用到了next数组,然后利用next数组的值来提高匹配速度,我首先讲一下next数组怎么求,之后再讲匹配方式。next数组详解首先是理解KM...
  • 判断题 1.假设模式是...1.在用KMP算法进行模式匹配时,模式ababaaababaa的next数组值为____。 选项 A -1,0,1,2,3,4,5,6,7,8,9,9 B -1,0,1,2,1,2,1,1,1,1,2,1 C -...
  • NEXT[]详解

    2020-05-13 09:50:48
    首先是理解KMP算法第一个难关是next数组每个值确定,这个问题困恼我很长时间,尤其是对照着代码一行一行分析,很容易把自己绕进去。 定义一字符 ptr = “ababaaababaa”; next[i](i从1开始算)代表着,除去...
  • KMP算法

    2016-05-06 23:51:12
    ababaaababaa的next数组为:011234223456 先从人的分析角度去分析怎么做。。。。 next数组下标从1开始计算 next[1] 肯定是 0 next[2] 肯定是 1 next[n] 的情况,将前面n-1个字符,计算从首尾开始组成最大...
  • KMP算法 - 求NEXT函数

    2016-11-21 11:53:57
    在数据结构与算法这门课中,我们接触到了KMP算法,一般使用KMP算法之前我们要求解一个NEXT函数值。  求解过程挺简单,我在这里... ababaaababaa的NEXT函数数组为________。    i 值 1  2  3  4  5
  • 【单选题】ababaaababaa的next数组为( )。【单选题】求解 Floyd算法的时间复杂度为( )【单选题】对题 8中的无向图G=(V,E)从 a 出发进行广度优先遍历,得到的顶点序列正确的是( )【单选题】在无向图 G的邻接表...
  • KMP~~算法+HDU1686

    2018-08-18 15:48:06
    KMP算法主要应用于字符串的匹配。 对于正常字符模式匹配,主长度为m,子串为n,时间...KMP算法用到了next数组,然后利用next数组的值来提高匹配速度,我首先讲一下next数组怎么求,之后再讲匹配方式。   ...
  • kmp(详解)

    2018-10-22 19:29:00
    对于正常字符模式匹配,主长度为m,子串为n,时间复杂度会到达O(m*n),而如果用KMP算法,复杂度将会减少线型时间O(m+n)。设主为ptr="ababaaababaa";...KMP算法用到了next数组,然后利用...

空空如也

空空如也

1 2
收藏数 22
精华内容 8
关键字:

串ababaaababaa的next数组