精华内容
下载资源
问答
  • 首先在将例子之前先说说这个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

    展开全文
  • KMP入门级别算法详解--终于解决了(next数组详解)

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

    对于正常的字符串模式匹配,主串长度为m,子串为n,时间复杂度会到达O(m*n),而如果用KMP算法,复杂度将会减少线型时间O(m+n)。

     

    设主串为ptr="ababaaababaa";,要比较的子串为a=“aab”;

     

    KMP算法用到了next数组,然后利用next数组的值来提高匹配速度,我首先讲一下next数组怎么求,之后再讲匹配方式。

     

    next数组详解

    首先是理解KMP算法的第一个难关是next数组每个值的确定,这个问题困恼我很长时间,尤其是对照着代码一行一行分析,很容易把自己绕进去。

    定义一串字符串

    ptr = "ababaaababaa";

     

    next[i]i从1开始算)代表着,除去第i个数,在一个字符串里面从第一个数到第(i-1)字符串前缀与后缀最长重复的长度。(这里看不懂继续往下看就行)

     

    什么是前缀

    在“aba”中,前缀就是“ab”,除去最后一个字符的剩余字符串。

    同理可以理解后缀。除去第一个字符的后面全部的字符串。

     

    在“aba”中,前缀是“ab”,后缀是“ba”,那么两者最长的子串就是“a”;

    在“ababa”中,前缀是“abab”,后缀是“baba”,二者最长重复子串是“aba”;

    在“abcabcdabc”中,前缀是“abcabcdab”,后缀是“bcabcdabc”,二者最长重复的子串是“abc”;

     

    这里有一点要注意,前缀必须要从头开始算,后缀要从最后一个数开始算,中间截一段相同字符串是不行的。

     

    在next数组中,有两种定义方式:(定义方式可以先不用管,继续往下看,看懂了再回来看)

    第一种是next[1]=-1,next[2]=-1。这里的-1代表没有匹配,1代表匹配了1位。

    第二种是规定next[1]=0,next[2]=1。(第二种方法之后会讲)这里0与1是规定,后面的匹配中,如果1位匹配,则规定next值为2(就是匹配的位数+1)。

     

    先看第一种规定方法:

    再回到next[i]的定义,对于字符串ptr = "ababaaababaa";

    next[1] = -1,字符串“a”,要进行next数组运算,也就是代表着除了第一个元素,它本身之前的 前缀 与 后缀 最长的重复子串,这里是空 ,即"",没有,我们记为-1,代表空。(0代表1位相同,1代表两位相同,依次累加)。

    next[2] = -1,字符串为“ab”,要进行计算的字符串为“a”(要扣除当前字符“b”,所以只剩下“a”),没有前缀与后缀,故最长重复的子串是空,值为-1;

    next[3] = -1,字符串为“aba”,要进行计算的字符串为“ab”(要扣除当前字符“a”,所以只剩下“ab”),前缀是“a”,后缀是“b”,最长重复的子串“”;

    next[4] = 1,字符串为“abab”,要进行计算的字符串为"aba"(要扣除当前字符“b”,所以只剩下“aba”),前缀是“ab”,后缀是“ba”,最长重复的子串“a”;next数组里面就是最长重复子串字符串的长度

    next[5] = 2,字符串为“ababa”,要进行计算的字符串为"abab"(要扣除当前字符“a”,所以只剩下“abab”),前缀是“aba”,后缀是“bab”,最长重复的子串“ab”;

    next[6] = 3,字符串为“ababaa”,要进行计算的字符串为"ababa"(要扣除当前字符“a”,所以只剩下“ababa”),前缀是“abab”,后缀是“baba”,最长重复的子串“aba”;

    next[7] = 1,字符串为“ababaaa”,要进行计算的字符串为"ababaa"(要扣除当前字符“a”,所以只剩下“ababaa”),前缀是“ababa”,后缀是“babaa”,最长重复的子串“a”;

    next[8] = 1,字符串为“ababaaab”,要进行计算的字符串为"ababaaa"(要扣除当前字符“b”,所以只剩下“ababaaa”),前缀是“ababaa”,后缀是“babaaa”,最长重复的子串“a”;

    next[9] = 2,字符串为“ababaaaba”,要进行计算的字符串为"ababaaab"(要扣除当前字符“a”,所以只剩下“ababaaab”),前缀是“ababaaa”,后缀是“babaaab”,最长重复的子串“ab”;

    next[10] = 3,字符串为“ababaaabab”,要进行计算的字符串为"ababaaaba"(要扣除当前字符“b”,所以只剩下“ababaaaba”),前缀是“ababaaab”,后缀是“babaaaba”,最长重复的子串“aba”;

    next[11] = 4,字符串为“ababaaababa”,要进行计算的字符串为"ababaaabab"(要扣除当前字符“a”,所以只剩下“ababaaabab”),前缀是“ababaaaba”,后缀是“babaaabab”,最长重复的子串“abab”;

    next[12] = 5,字符串为“ababaaababaa”,要进行计算的字符串为"ababaaababa"(要扣除当前字符“a”,所以只剩下“ababaaababa”),前缀是“ababaaabab”,后缀是“babaaaababa”,最长重复的子串“ababa”;

    所以字符串ptr = "ababaaababaa"的next数组为:-1,-1,-1,1,2,3,1,1,2,3,4,5

     

    第二种方法中:

    变化的只有下标,原理都一样。

    这里我们定义next[1] = 0 , next[1] = 1;

     

    再分析ptr字符串,ptr = "ababaaababaa";

    跟上一个的情况类似,

     

    next[1] = 0 ,事先定义好的

    next[2] = 1 ,事先定义好的

    next[3] = 1 ,最长重复的子串“”;1代表没有重复,2代表有一个字符重复。

    next[4] = 2 ,最长重复的子串“a”;追偿的长度加1,即为2.

    next[5] = 3 ,以下都跟之前的一样,这种方法是最长的长度再加上一就可以了。

    next[6] = 4

    next[7] = 2

    next[8] = 2

    next[9] = 3

    next[10] = 4

    next[11] = 5

    next[12] = 6

     

    以上是next数组的详细解释。next数组求值 是比较麻烦的,剩下的匹配方式就很简单了。

    next数组用于子串身上,根据上面的原理,我们能够推出子串a=“aab”的next数组的值分别为0,1,2.(按照我说的第二种方式算的)。

    首先开始计算主串与子串的字符,设置主串用i来表示,子串用j来表示,如果ptr[i]与a[i]相等,那么i与j就都加1

    prt[1]与a[1]相等,i++,j++:

    用代码实现就是

    if( j==0 ||  ptr[i]==a[j])
    {
        ++i;
        ++j;
    }

     

    ptr[2]与a[2]不相等

    此时ptr[2]!=a[2],那么令j = next[j],此时j=2,那么next[j] = next[2] = 1.那么此时j就等于1.这一段判断用代码解释的话就是:

    if( ptr[i]!=a[j])
    {
          j = next[j];
    }

    加上上面的代码进行组合:

    在对两个数组进行比对时,各自的i,j取值代码:

    while( i<ptr.length && j< a.length)
    {
         if( j==0 || ptr[i]==a[i] )
        {
              ++i;
              ++j;
              next[i] = j;
        }
        else
        {
              j = next[j];
        }
    }

     

    此时将a[j]置于j此时所处的位置,即a[1]放到j=2处,因为在j=2时出现不匹配的情况。

    此时再次计算是否匹配,可以看出来a[1]!=ptr[2],那么j = next[j],即此时j = next[1] = 0;

    根据上面的代码,当j=0时,执行++i;++j;

    此时就变为:

    此时ptr[3] = a[1],继续向下走,下一个又不相等了,然后“aab”向后挪一位,这里不再赘述了,主要的思想已经讲明白了。到最后一直到i = 8,j=3时匹配成功,KMP算法结束。整个过程就结束了。

    展开全文
  • 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;
    展开全文
  • next数组求解详解

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

    next数组的求解方法是:

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

    这段话一开始看了好几遍都没彻底理解,看了好几个帖子,终于搞明白next数组具体如何求解。还是以例子说明具体求解过程
    假设求串′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

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

    展开全文
  • 算法:next数组的求法详解

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

    千次阅读 2015-09-13 20:49:48
     next数组的求解方法是:第一位的next值0,第二位的next值1,后面求解每一位的next值时,根据前一位进行比较。首先将前一位与其next值对应的内容进行比较,如果相等,则该位的next值就是前一位的next值加上1;...
  • next数组两种求法

    万次阅读 多人点赞 2018-08-22 15:03:37
    (1)看到网上同一个字符串求 next 数组的值有两种,一种是 -1 开头,一种是 0 开头,虽然有差别,但是以 0 开头的next数组的每一项都比以 -1 开头的next数组的对应项大1,所以,具体是以 0 开头还是以 -1 开头看...
  • 假设求串′ababaaababaa′的next数组 模式串ababaaababaa ...1、前两位:next数组前两位一定是0,1 即前两位ab对应的next数组为01,则: 模式串ababaaababaa 下标 1 2 3 4 5 6 7 ...
  • 这篇博客发出来只是为了应付明天的数据结构考试,如有错误欢迎指正! 《数据结构C语言版第2版》的课后习题里有这两道题(答案是CA) 书上求next数组和nextval数组的代码如下: ...计算ababaaababaanext数组: ne
  • 利用KMP算法分别求出next数组和nextval数组 分析: 数组索引:0-n 逻辑索引:1-n next数组: 1、next[0]=0,next[1]=1; 2、当判断一个字母X的next值时,需要将前一个位置的字母Y和其next值m相同的逻辑索引的字母Z...
  • next数组详解

    千次阅读 2020-05-20 00:20:37
    next数组详解思路前缀、后缀、部分匹配值部分匹配(Partial Match,PM)表next数组求解方法代码实现 前缀、后缀、部分匹配值 "前缀"指除了最后一个字符以外,字符串的所有头部组合; "后缀"指除了第一个字符以外,...
  • 一、说明 (1)看到网上同一个字符串求 next 数组的值有两种,一种是 -1 开头,一种是 0 开头,虽然有差别,但是以 0 开头的next数组的每一项都比以 -1 开头的next数组的对应项大1,所以,具体是以 0 开头还是以 -1...
  • 数据结构之next数组求法

    千次阅读 2020-12-18 23:17:37
    我们能确定next数组第一二位一定分别0,1,后面求解每一位的next值时,根据前一位进行比较。从第三位开始,将前一位与其next值对应的内容进行比较,如果相等,则该位的next值就是前一位的next值加上1;如果不等,...
  • next数组介绍及实例

    千次阅读 2018-01-07 15:33:29
    本文转自他人。... 提示:切记!!!是前一位的next对应的值 与其自身比较。而这里的next 的值就是...next数组的求解方法是: 第一位的next值0,第二位的next值1,后面求解每一位的next值时,根据前一位进行比较
  • 求KMP算法的next数组 今天刷到一个笔试题,求一个字符串在KMP算法下的next数组 几番百度和看题解,居然大多数的题解都有毛病被一顿吐槽 最后,通过一张动图搞懂了计算的原理 如下: 本图来自这个博客 正如下面评论...
  • next数组的求解方法是: 第一位的next值0,第二位的next值1,后面求解每一位的next值时,根据前一位进行比较。首先将前一位与其next值对应的内容进行比较,如果相等,则该位的next值就是前一位的next值加上1;...
  • KMP算法理解之next数组

    2018-09-20 15:03:10
    .next数组的求法(这个是真的有点困难的。。。还好自己又搞明白了) 下面以字符串ababaaababaa为例说明一下 next[i](i从1开始算)代表着,除去第i个数,在一个字符串里面从第一个数到第(i-1)字符串前缀与后缀...
  • KMP 算法我们有写好的函数帮我们计算 Next 数组的值和 Nextval 数组的值,但是如果是考试,那就只能自己来手算这两个数组了,这里分享一下我的计算方法吧。 计算前缀 Next[i] 的值: 我们令 next[0] = -1 。从 next...
  •  谈到next字符串匹配,自然就想到kmp字符串匹配算法,可以说next数组是kmp算法中的一种,当然小编觉得next比较简单首先写下来。  一、next数组是什么  next数组的理解之前,你要明白什么是kmp算法,kmp算法又称...
  • KMP算法的next数组

    2015-11-28 20:17:27
    关于字符串匹配里,KMP算法中next实现实现原理。关于字符串匹配里,KMP算法中next实现实现原理。
  • KMP算法是模式匹配专用算法。 它是在已知模式串的next或nextval数组的基础上执行的。如果不知道它们二者之一,就没法使用KMP算法,因此我们需要计算它们。...KMP算法中有next数组和nextval数组之分。...
  • private static int[] getNext(String s) { //传过来的是模式串,返回的是next数组 int len = s.length(); //获取模式串的长度 char[] p = s.toCharArray(); //把模式串转换成char数组 int[] ne
  • next数组nextval值

    千次阅读 2017-06-12 15:52:42
    模式串‘aaaab’和‘adabbadada’ next和nextval数组值 记得大学时自己也总结出了这种算法的,手动计算,数据结构的书都丢了,还好在网上找会了同样的算法 特记下: int get_nextval(SString T,int...
  • KMP 中next数组求解方法 参考书:数据结构C语言版(第二版)转载:https://blog.csdn.net/wenyun_kang/article/details/65436838?locationNum=13&amp;fps=1转载:...
  • Cyclic Nacklace  节省篇幅不粘题面了。。。  看懂题后脑袋里略过KMP,学过但没怎么用过,又直接跳下...用next数组求出自身最大匹配,剩下的即循环节的长度。然后用剩下的长度除去最大匹配中循环节的长度即可。
  • KMP算法及next数组

    2017-08-15 19:48:10
    算法解决的问题: 主要是字符串匹配。给你两个字符串,寻找其中一个字符串是否包含另一个字符串,如果包含,返回包含的起始位置 ,学长给的模板就是这种问题。目前只会做水题,所以也没碰到其他的... 1 a标记第一个
  • #include &lt;iostream&gt; #include &lt;string&gt; #include &...void get_next(char* T,int *next)//C语言版本 {  int i = 1, j = 0;  next[1] = 0;  while (i &lt; T[0]) ...

空空如也

空空如也

1 2 3 4 5 ... 9
收藏数 163
精华内容 65
关键字:

ababaaababaa的next数组为