精华内容
下载资源
问答
  • next数组和nextval数组值 千次阅读 多人点赞
    2021-08-27 18:57:37

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

    序号123456789101112
    ababaaababaa
    next011234223456
    1. 无脑第一位第二位是0和1。
    2. 计算第三位:看第二位b的next值,为1,把b和1对应的a进行比较,不同,则第三位a的next值为1,因为一直比到最前一位,都没有发生比较相同的现象。
    3. 计算第四位:看第三位a的next值,为1,把a和1对应的a进行比较,相同,则第四位b的next值为第三位a的next值加1,为2。
    4. 计算第五位:看第四位b的next值,为2,把b和2对应的b进行比较,相同,则第五位a的next值为第四位b的next值加1,为3。
    5. 计算第六位:看第五位a的next值,为3,把a和3对应的a进行比较,相同,则第六位a的next值为第五位a的next值加1,为4.
    6. 计算第七位:看第六位a的next值,为4,把a和4对应的b进行比较,不同,则再将4对应的b的next值2所对应的b与第六位a比较,不同,则再将2对应的b的next值1所对应的a与第六位a比较,相同,则第七位a的next值为第二位的next值加1,为2。
    7. 计算第八位:看第七位a的next值,为2,把a和2对应的b进行比较,不同,则再将2对应的b的next值1所对应的a进行比较,相同,则第八位的next值为第二位next值加1,为2。
    8. 计算第九位:看第八位b的next值,为2,把b和2对应的b进行比较,相同,则第九位的next值为第八位next值加1,为3.

    求nextval得先求出next值
    第一位为0,然后从左到右,计算哪一位,就把哪一位的next值所对应的值和本位相比较,若不同,nextval值就为本身的next值;若相同,nextval值就为next值所对应的nextval值。

    序号123456789101112
    ababaaababaa
    next011234223456
    nextval010104210104
    1. 第一个为0。
    2. 计算第二位:第二位b的next值为1,把1对应的a和b比较,不同,则第二位的nextval值为本身的next值,为1。
    3. 计算第三位:第三位a的next值为1,把1对应的a和a比较,相同,则第三位的nextval值为第一位的nextval值,为0。
    4. 计算第四位,第四位b的next值为2,把2对应的b和b比较,相同,则第四位的nextval值为第二位的nextval值,为1。
    5. 计算第五位:第五位a的next值为3,把3对应的a和a比较,相同,则第五位的nextval值为第三位的nextval值,为0。
    6. 计算第六位:第六位a的next值为4,把4对应的b和a比较,不同,则第六位的nextval值为本身的next值,为4。
    7. 计算第七位:第七位a的next值为2,把2对应的b和a比较,不同,则第七位的nextval值为本身的next值,为2。
    8. 计算第八位:第八位b的next值为2,把2对应的b和b比较,相同,则第八位的nextval值为第二位的nextval值,为1。
    9. 计算第九位:第九位a的next值为3,把3对应的a和a比较,相同,则第九位的nextval值为第三位的nextval值,为0。
    更多相关内容
  • 在复习数据结构课程的过程中 对kmp算法及next数组的求解过程进行了深度探索 内含具体代码 及求解next数组的详解 望对大家有所帮助
  • 求解nextnext数组的求解方法:首先第一位的next值直接给0,第二位的next值直接给1,后面求解每一位的next值时,都要前一位进行比较。首先将前一位与其next值的对应位进行比较,若相等,则该位的next值就是前一位的...

    一. 求解next

    next数组的求解方法:首先第一位的next值直接给0,第二位的next值直接给1,后面求解每一位的next值时,都要前一位进行比较。首先将前一位与其next值的对应位进行比较,若相等,则该位的next值就是前一位的next值加上1;若不等,继续重复这个过程,直到找到相等某一位,将其next值加1即可,如果找到第一位都没有找到,那么该位的next值即为1。

    故事助记:「检查作业」—— 这次是几分呢?

    手里拿个小本,看左边的题目的结果,根据这个结果给出的位置找答案,哦一样的,在这个结果基础上加1分;哦不一样啊,以当前这个结果作为新结果,以新结果给出的位置继续找,重复进行,如果找到了,就在新结果基础上加1分;如果找不到,那就勉强给1分。

    举例:

    21e5816baf9a

    next数组求解示例

    求解步骤:

    1.前两位必为0,1。

    2.计算第三位的时候,看第二位b的next值,为1,则把b和1对应的a进行比较,不同,则第三位a的next的值为1,因为一直比到最前一位,都没有发生比较相同的现象。

    3.计算第四位的时候,看第三位a的next值,为1,则把a和1对应的a进行比较,相同,则第四位a的next的值为第三位a的next值加上1,为2。因为是在第三位实现了其next值对应的值与第三位的值相同。

    4.计算第五位的时候,看第四位a的next值,为2,则把a和2对应的b进行比较,不同,则再将b对应的next值1对应的a与第四位的a进行比较,相同,则第五位的next值为第二位b的next值加上1,为2。因为是在第二位实现了其next值对应的值与第四位的值相同。

    5.计算第六位的时候,看第五位b的next值,为2,则把b和2对应的b进行比较,相同,则第六位c的next值为第五位b的next值加上1,为3,因为是在第五位实现了其next值对应的值与第五位相同。

    6.计算第七位的时候,看第六位c的next值,为3,则把c和3对应的a进行比较,不同,则再把第3位a的next值1对应的a与第六位c比较,仍然不同,则第七位的next值为1。

    7.计算第八位的时候,看第七位a的next值,为1,则把a和1对应的a进行比较,相同,则第八位c的next值为第七位a的next值加上1,为2,因为是在第七位和实现了其next值对应的值与第七位相同。

    另解(不想看可跳过):

    求next数组:

    先求模式串S 每一个字符前面的那个字符串的最大公共前后缀长度,将这一系列长度存成一个数组,求出来的每个长度其实就是和模式串每一个对应位置上做比较的下标

    例如:模式串是ABACABC,其最长公共前后缀长度数组为:我们将最长公共前后缀长度记作LCPSF,现在从模式串第一个字符A开始,A的前面字符串为null,所以A之前的子串的LCPSF是0;来到B,B的前面字符串是A,A是单独的字符不存在公共前后缀,所以长度也是0;来到A,A前面的子串是AB,LCPSF为0;来到C,C前面的子串是ABA,LCPSF为1;来到A,A前面的子串是ABAC,LCPSF为0;来到B,B之前子串为ABACA,LCPSF为1;来到C,C前面子串为ABACAB,LCPSF为2;到此这个最长公共前后缀数组就出来了[0,0,0,1,0,1,2]将这个数组从第二个值开始每个值加1后,得到[0,1,1,2,1,2,3] 就是将要和子串对应位置比较的下标,即为next数组。

    二、求解nextval数组

    掌握了上面求next数组的方法后,我们可以迅速求得模式串ABACABC的next数组为[0,1,1,2,1,2,3],现在继续求模式串ABACABC的next-val数组:

    求解nextval数组是基于next数组的,模式串每一个位置的字符和其next数组值给出的下标的对应位置的数作比较,相等就取next-val中对应的next数组值作为当前位置字符的next-val值,不等就直接取当前位置字符的next数组的值作为next-val的值。

    故事助记:(nextval数组第一位始终是0,从第二位开始)妈妈都会告诉小朋友不要相信陌生人,确定nextval数组的问题就可以抽象为要不要拿别人东西吃的问题,每个小朋友心里都有自己想吃的东西(当前位置数组项),并且每位小朋友手里都有一个线索(next数组项对应每位小朋友手里的线索),当别人给自己东西吃的,就拿自己线索对应的别人的吃的东西做比较,如果线索对应的东西不是自己爱吃的,那就选择吃自己的东西(保留自己的线索),否则就吃别人的东西(把别人的线索拿过来)。

    求解步骤:

    next-val数组第一个数直接为0。

    next-val第二数:模式串第二个字符为B,对应的下标数组第二个数是1,那就是将模式串的第1个字符和B相比较,A!=B,所以直接将下标数组第二个数1作为next-val数组第二个数的值

    第三个数:模式串第三个字符为A,对应下标数组第三个数为1,取其作为下标,找到模式串第1个字符为A,A=A,那取next-val的第一个数做为next-val第三个数的值,也就是0

    举例:

    位置

    1

    2

    3

    4

    5

    6

    7

    模式串

    A

    B

    A

    C

    A

    B

    C

    next数组

    0

    1

    1

    2

    1

    2

    3

    nextval数组

    0

    1

    0

    2

    0

    1

    3

    注意,这里所有序号,第一个位置都是1开始

    三、next 和 nextval 比较

    next数组的缺陷举例如下:

    比如主串是"aabXXXXXXXXXXXXXX",模式串"aac"

    通过计算 "aac" 的next数组为012,当模式串在字符c上失配时,会跳到第2个字符,然后再和主串当前失配的字符重新比较,即此处用模式串的第二个a和主串的b比较,即 "aabXXXXXXXXXXXXXX"vs"aac",显然a也不等于b。然后会跳到1接着比,直到匹配成功或者匹配失败主串后移一位。

    而"aac"的nextval数组为002 当在c失配时会跳到2,若还失配就直接跳到0,比next数组少比较了1次。

    在如果模式串很长的话,那可以省去很多比较,因此使用nextval数组比next数组高效。

    四、问题思考:

    在模式匹配的KMP算法中,求模式的next数组值(也称为KMP算法中失败函数)定义如下:

    21e5816baf9a

    next数组的定义

    (1)当j=1时,为什么要取next[1]=0?

    答:当模式串第一个字符与主串中某字符不匹配时,主串指针应移至下一字符,再和模式串第一个字符比较。(next[1]=0 表示模式串中已没有字符可与主串中当前字符 s[i] 比较)

    (2)为什么要取 max{k},k最大是多少?

    答:当主串中第 i 个字符与模式串中第 j 个字符不匹配时,若主串 i 不回溯,则假定模式串中第 k 个字符与主串中第 i 个字符比较,k 值应满足条件 1

    (3)其它情况是什么?为什么取 next[j] = 1?

    答:以上两种情况的不匹配,主串指针不回溯,在最坏的情况下,模式串从第 1 个字符开始与主串第 i 个字符比较,以便不丢失可能的匹配。

    展开全文
  • next数组详解

    千次阅读 2020-05-20 00:20:37
    next数组详解思路前缀、后缀、部分匹配值部分匹配(Partial Match,PM)表next数组求解方法代码实现 前缀、后缀、部分匹配值 "前缀"指除了最后一个字符以外,字符串的所有头部组合; "后缀"指除了第一个字符以外,...

    前缀、后缀、部分匹配值

    "前缀"指除了最后一个字符以外,字符串的所有头部组合;
    "后缀"指除了第一个字符以外,字符串的所有尾部组合。
    “部分匹配值”是"前缀"和"后缀"的最长的共有元素的长度

    以"abcdabd"为例

    - "a"的前缀和后缀都为空集,共有元素的长度为0;

    - "ab"的前缀为[a],后缀为[b],共有元素的长度为0;

    - "abc"的前缀为[a, ab],后缀为[bc, c],共有元素的长度0;

    - "abcd"的前缀为[a, ab, abc],后缀为[bcd, cd, d],共有元素的长度为0;

    - “abcda"的前缀为[a, ab, abc, abcd],后缀为[bcda, cda, da, a],共有元素为"a”,长度为1;

    - “abcdab"的前缀为[a, ab, abc, abcd, abcda],后缀为[bcdab, cdab, dab, ab, b],共有元素为"ab”,长度为2;

    - "abcdabd"的前缀为[a, ab, abc, abcd, abcda,abcdab],后缀为[bcdabd, cdabd, dabd, abd, bd,d],共有元素的长度为0。

    部分匹配(Partial Match,PM)表

    下标01234567891011
    模式串 Tababaaababaa
    PM值001231123456

    next数组求解方法

    已知串T=“ababaaababaa”;

    一、模式串的下标从0开始,此种方式的next数组求解方式:

    此种方式的next数组就是上述PM值右移一位,空出的下标为0的位置赋值为-1(此处的-1是为了方便判断,也可以是其他值,自己斟酌即可)

    下面从代码的角度讲述一下求解next[]的思路:
    
    1、首先可以确定  next[0] = -1;  next[1] = 0; 后面求解每一位的next值时,根据前一位进行比较。
    2、从第三位开始,也就是从T[2]开始,比较前一位元素与其next值对应的元素是否相同
    3、若相同,则所求next值就等于前一位元素对应的next值 +1
    4、若不同,则向前继续寻找next值对应的元素与前一位进行比较,直到找到与前一位元素相同的元素,
       若找到,则找到的这个位置的next值+1 就是我们所求的next值
    5、若直到第一个元素,都没有找到与前一位元素相同的元素,则所求next值为0
    

    1、可以确定前两位的值:next[0] = -1 ,next[1] = 0;

    下标01234567891011
    模式串 Tababaaababaa
    next[ ]-10

    2、看第三位,也就是T[2],看T[2]的前一位T[1]对应元素是b,T[1]所对应的next值是0,0对应的元素是a,b与a不同,继续向前寻找next值,也就是找T[0]的next值为-1,表示T[1]之前没有找到与自身相等的元素,则第三位T[2]=a的next值为0,也就是next[2]=0

    下标01234567891011
    模式串 Tababaaababaa
    next[ ]-100

    3、看第四位,也就是T[3],看T[3]的前一位T[2]对应元素是a,T[2]所对应的next值是0,0对应的元素是a,a与a相同,则T[3]对应的next值就是T[2]的next值+1 ,next[3] = 1;

    下标01234567891011
    模式串 Tababaaababaa
    next[ ]-1001

    4、看第五位,也就是T[4],看T[4]的前一位T[3]对应元素是b,T[3]所对应的next值是1,1对应的元素是b,b与b相同,则T[4]对应的next值就是T[3]的next值+1 ,next[4] = 2;

    下标01234567891011
    模式串 Tababaaababaa
    next[ ]-10012

    5、看第六位,也就是T[5],看T[5]的前一位T[4]对应元素是a,T[4]所对应的next值是2,2对应的元素是a,a与a相同,则T[5]对应的next值就是T[4]的next值+1 ,next[5] = 3;

    下标01234567891011
    模式串 Tababaaababaa
    next[ ]-100123

    6、看第七位,也就是T[6],看T[6]的前一位T[5]对应元素是a,T[5]所对应的next值是3,3对应的元素是b,a与b不同,则向前继续寻找next值,找到T[3]对应的next值是1,1对应的元素是b,a与b不同,继续向前寻找next值,T[1]对应的next值是0,0对应的元素是a,a与a相同,则T[6]对应的next值就是T[1]的 next值 +1,next[6] = 1;

    下标01234567891011
    模式串 Tababaaababaa
    next[ ]-1001231

    7、看第八位,也就是T[7],看T[7]的前一位T[6]对应元素是a,T[6]所对应的next值是1,1对应的元素是b,a与b不同,则向前继续寻找next值,T[1]对应的next值是0,0对应的元素是a,a与a相同,则T[7]对应的next值就是T[1]的 next值 +1,next[7] = 1;

    下标01234567891011
    模式串 Tababaaababaa
    next[ ]-10012311

    8、看第九位,也就是T[8],看T[8]的前一位T[7]对应元素是b,T[7]所对应的next值是1,1对应的元素是b,b与b相同,则T[8]对应的next值就是T[7]的 next值 +1,next[8] = 2;

    下标01234567891011
    模式串 Tababaaababaa
    next[ ]-100123112

    9、看第十位,也就是T[9],看T[9]的前一位T[8]对应元素是a,T[8]所对应的next值是2,2对应的元素是a,a与a相同,则T[9]对应的next值就是T[8]的 next值 +1,next[9] = 3;

    下标01234567891011
    模式串 Tababaaababaa
    next[ ]-1001231123

    10、看第十一位,也就是T[10],看T[10]的前一位T[9]对应元素是b,T[9]所对应的next值是3,3对应的元素是b,b与b相同,则T[10]对应的next值就是T[9]的 next值 +1,next[10] = 4;

    下标01234567891011
    模式串 Tababaaababaa
    next[ ]-10012311234

    11、看第十二位,也就是T[11],看T[11]的前一位T[10]对应元素是a,T[10]所对应的next值是4,4对应的元素是a,a与a相同,则T[11]对应的next值就是T[10]的 next值 +1,next[11] = 5;

    下标01234567891011
    模式串 Tababaaababaa
    next[ ]-100123112345

    二、模式串下标从1开始,此种方式的next数组求解方式

    此种方式的next数组就是上述PM值右移一位,空出的下标为0的位置赋值为-1,然后所有值整体+1得到next数组

    下面从代码的角度讲述一下求解next[]的思路:
    
    1、首先可以确定  next[1] = 0;  next[2] = 1 ; 后面求解每一位的next值时,根据前一位进行比较。 
    2、从第三位开始,也就是从T[3]开始,比较前一位元素与其next值对应的元素是否相同
    3、若相同,则所求next值就等于前一位元素对应的next值 +1
    4、若不同,则向前继续寻找next值对应的元素与前一位进行比较,直到找到与前一位元素相同的元素,
       若找到,则找到的这个位置的next值+1 就是我们所求的next值
    5、若直到第一个元素,都没有找到与前一位元素相同的元素,则所求next值为1
    

    1、可以确定前两位的值:next[1] = 0 ,next[2] = 1;

    下标123456789101112
    模式串 Tababaaababaa
    next[ ]01

    2、看第三位,也就是T[3],看T[3]的前一位T[2]对应元素是b,T[2]所对应的next值是1,1对应的元素是a,b与a不同,继续向前寻找next值,也就是找T[1]的next值为0,0没有对应的元素,表示没有找到与T[2]也就是b相等的元素,则第三位T[3]的next值为1,也就是next[3]=1

    下标123456789101112
    模式串 Tababaaababaa
    next[ ]011

    3、看第四位,也就是T[4],看T[4]的前一位T[3]对应元素是a,T[3]所对应的next值是1,1对应的元素是a,a与a相同,则T[4]对应的next值就是T[3]的next值+1 ,next[4] = 2;

    下标123456789101112
    模式串 Tababaaababaa
    next[ ]0112

    4、看第五位,也就是T[5],看T[5]的前一位T[4]对应元素是b,T[4]所对应的next值是2,2对应的元素是b,b与b相同,则T[5]对应的next值就是T[4]的next值+1 ,next[5] = 3;

    下标123456789101112
    模式串 Tababaaababaa
    next[ ]01123

    5、看第六位,也就是T[6],看T[6]的前一位T[5]对应元素是a,T[5]所对应的next值是3,3对应的元素是a,a与a相同,则T[6]对应的next值就是T[5]的next值+1 ,next[6] = 4;

    下标123456789101112
    模式串 Tababaaababaa
    next[ ]011234

    6、看第七位,也就是T[7],看T[7]的前一位T[6]对应元素是a,T[6]所对应的next值是4,4对应的元素是b,a与b不同,则向前继续寻找next值,找到T[4]对应的next值是2,2对应的元素是b,a与b不同,继续向前寻找next值,T[2]对应的next值是1,1对应的元素是a,a与a相同,则T[7]对应的next值就是T[2]的 next值 +1,next[7] = 2;

    下标123456789101112
    模式串 Tababaaababaa
    next[ ]0112342

    7、看第八位,也就是T[8],看T[8]的前一位T[7]对应元素是a,T[7]所对应的next值是2,2对应的元素是b,a与b不同,则向前继续寻找next值,T[2]对应的next值是1,1对应的元素是a,a与a相同,则T[7]对应的next值就是T[2]的 next值 +1,next[8] = 2;

    下标123456789101112
    模式串 Tababaaababaa
    next[ ]01123422

    8、看第九位,也就是T[9],看T[9]的前一位T[8]对应元素是b,T[8]所对应的next值是2,2对应的元素是b,b与b相同,则T[9]对应的next值就是T[8]的 next值 +1,next[9] = 3;

    下标123456789101112
    模式串 Tababaaababaa
    next[ ]011234223

    9、看第十位,也就是T[10],看T[10]的前一位T[9]对应元素是a,T[9]所对应的next值是3,3对应的元素是a,a与a相同,则T[10]对应的next值就是T[9]的 next值 +1,next[10] = 4;

    下标123456789101112
    模式串 Tababaaababaa
    next[ ]0112342234

    10、看第十一位,也就是T[11],看T[11]的前一位T[10]对应元素是b,T[10]所对应的next值是4,4对应的元素是b,b与b相同,则T[11]对应的next值就是T[10]的 next值 +1,next[11] = 5;

    下标123456789101112
    模式串 Tababaaababaa
    next[ ]01123422345

    11、看第十二位,也就是T[12],看T[12]的前一位T[11]对应元素是a,T[11]所对应的next值是5,5对应的元素是a,a与a相同,则T[12]对应的next值就是T[11]的 next值 +1,next[12] = 6;

    下标123456789101112
    模式串 Tababaaababaa
    next[ ]011234223456

    注意:这两种方式的细微差别,整体思路一致,注意next起始位置以及没有找到与前一位元素相同的元素时,next赋值问题,可赋值0或1,根据自己实际情况选择

    代码实现

    第一种:字符数组下标从0开始的代码如下:

    /**
     * 求next数组 :字符数组下标从0开始
     * next数组是模式串的部分匹配值整体右移一位,第一位赋值-1得到的数组
     *  注意:若字符数组下标从1开始,则
     *  next数组即是 模式串的部分匹配值整体右移一位,第一位赋值-1,数组整体再+1 所得到的数组
     *
     */
    
    void getNext(char T[],int TLength) {
        int next[TLength];
        next[0] = -1;
        printf("next[0] = %d \n", next[0]);
        int i = 0, j = -1;//i表示数组下标,初始化为0;j表示next数组的值,初始化为-1
        while (i < TLength -1) {
            /**
             * ①若j=-1表示没有找到相同的元素,所求next值应置为0
             * ②若T[i] == T[j] 表示找到了相等的元素,此时找到的这个位置的next值+1就是所求next值
             */
            if (j == -1 || T[i] == T[j]) {
                i++;
                j++;
                next[i] = j;
                printf("next[%d] = %d \n",i, next[i]);
            }else{
                j = next[j] ;
            }
        }
    }
    int main(){
        char T[] = {'a','b','a','b','a','a','a','b','a','b','a','a'};
        int TLength = 12;
        getNext(T,12);
        return 0;
    }
    

    测试结果:

    next[0] = -1
    next[1] = 0
    next[2] = 0
    next[3] = 1
    next[4] = 2
    next[5] = 3
    next[6] = 1
    next[7] = 1
    next[8] = 2
    next[9] = 3
    next[10] = 4
    next[11] = 5
    

    第二种:字符数组下标从1开始的代码如下:

    void getNext(char T[],int TLength) {
        int next[TLength];
        next[1] = 0;
        printf("next[1] = %d \n", next[1]);
        int i = 1, j = 0;//i表示数组下标,初始化为1;j表示next数组的值,初始化为0
        while (i < TLength - 1) {
            /**
             * ①若j=0表示没有找到相同的元素,所求next值应置为1
             * ②若T[i] == T[j] 表示找到了相等的元素,此时找到的这个位置的next值+1就是所求next值
             */
            if (j == 0 || T[i] == T[j]) {
                i++;
                j++;
                next[i] = j;
                printf("next[%d] = %d \n",i, next[i]);
            }else{
                j = next[j] ;
            }
        }
    }
    int main(){
        char T[] = {'*','a','b','a','b','a','a','a','b','a','b','a','a'};
        int TLength = 13;
        getNext(T,13);
        return 0;
    }
    

    测试结果:

    next[1] = 0
    next[2] = 1
    next[3] = 1
    next[4] = 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赋值问题,可赋值0或1,根据自己实际情况选择

    展开全文
  • 刚刚开始遇到这个问题说实话完全...首先在将例子之前先说说这个next数组求解的思路:第一位的next的值是0,第二位的next的值为1,后面求解每一位的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数组求法详解理论基础PMT值的生成next数组的生成 在网上有很多kmp算法的讲解,大概的框架讲的都还不错,但在next数组的讲解上,我觉得不是很清晰。 在学习KMP算法时,next数组的求解是它的精髓。 在博客...
  • KMP算法之next数组详解

    千次阅读 多人点赞 2020-12-03 22:17:02
    KMP算法之next数组详解 KMP算法实现原理 KMP算法是一种非常高效的字符串匹配算法,下面我们来讲解一下KMP算如何高效的实现字符串匹配。我们假设如下主串和模式串: int i;//i表示主串的下标 int j;//j表示模式串的...
  • 作为408考生,数据结构绕不开KMP算法,网上各种求next数组的方法和结果竟各有不同,本文将带你探讨产生这种局面的原因和求next数组的两种方法。
  • KMP算法&next数组详解

    千次阅读 2020-10-28 13:13:12
    文章目录KMP算法详解前言一、示例二、用朴素的字符串匹配算法三、KMP算法实现1、KMP算法思路2、next数组的本质3、next数组带入思路实现4、next数组的求法4、代码实现C语言实现Java语言实现 前言 KMP算法是目前字符...
  • next数组两种求法

    万次阅读 多人点赞 2018-08-22 15:03:37
    (1)看到网上同一个字符串求 next 数组的值有两种,一种是 -1 开头,一种是 0 开头,虽然有差别,但是以 0 开头的next数组的每一项都比以 -1 开头的next数组的对应项大1,所以,具体是以 0 开头还是以 -1 开头看...
  • next数组的两种求法详解及完整代码

    多人点赞 热门讨论 2022-04-14 16:55:16
    求字符串的next数组: 方法一: 这里我们将next数组第1,2位分别设为0,1(还有-1,0这种设法,这里先将其设为0,1若有需要再减一即可) 后面求解每一位的next值时,根据前一位进行比较。 从第三位开始,将前一位与其...
  • 完成上面的例题是否对next数组又有了一些了解,同时我们也可以看到例题中next数组的一些特点 1:next[0]默认等于-1 (有些方法也等于0,下标顺序是从1开始,我们的方法下标顺序从0开始) 2:如果存在前后有相同字符...
  • next数组的计算方式

    2021-11-17 16:36:57
    i 0 1 2 3 4 5 6 7 8 9 10 11... 总结: 1、next数组首个位置数值为定值-1 2、next[i]的值是看在s[i]之前的字符串中重复的子串长度(1、不统计第i位置的字符2、两个子串一个必须从首位置开始,另一个必须从尾位置结束)
  • 首先你要知道手写next数组next数组与主串无关,只与模式串有关。 举个简单的例子 模式串是A B A B A A B现在手写next数组 next -1 0 0 1 2 3 0 如上面所示,如果要求红色字母位置的next值,只要把前面5个字符写...
  • 关于KMP算法next数组的改进——nextval数组
  • 求串′ababaaababaa′的next数组 模式串 a b a b a a a b a b a a 下标 1 2 3 4 5 6 7 8 9 10 11 12 next[1] = 0 next[2] = 1 ...
  • 算法:next数组的求法详解

    万次阅读 多人点赞 2019-01-27 16:26:48
    在牛客网刷题遇到了求next数组的题型,结果在学校学的没有牢记,做错了,还是要多刷题做总结啊。 我们先口述说明一下next数组的求解方法: 我们能确定next数组第一二位一定分别为0,1,后面求解每一位的next值时,...
  • 由于网上各种KMP算法的教程,对于next数组的求解都很简略。本人在学习的时候感到十分费解,于是便有了这篇文章 算法原理 求next[j+1],则已知next[1],next[2]…next[j] 假设next[j]=k1,则有P1~Pk1-1=Pj-k1+1~Pj-...
  • next数组如何求解

    2020-10-08 11:32:17
    next数组示例 我们先来看两个next数组的例子 示例1 j 1 2 3 4 5 6 模式串 a b c d e x next[j] 0 1 1 1 1 1 示例2 j 1 2 3 4 5 6 模式串 a b c a b x next[j] 0 1 1 1 2 3 求解方式 初始...
  • } } //next数组 int get_next(String* t, int* next) { int i, j; i = 1; j = 0; next[1] = 0; while (i < t->length) { if (j == 0 || t[i] == t[j]) { ++i; ++j; next[i] = j; } else { ...
  • 数据结构KMP算法很烦很抽象?next数组看不懂?nextval数组更是雾?阅读本文保证给您耳目一新的感觉。
  • KMP算法详解及next数组代码解释

    千次阅读 2020-03-27 16:20:23
    KMP算法详解及next数组代码解释 KMP算法理解起来并不算太过于困难,从图像实例可以很直观得明晰算法原理,难点在于理解KMP算法中生成next数组的代码: void next(char *s,int *next) { int k = -1; int j = 0; ...
  • KMP算法、next数组、nextval数组代码实现(C语言版) 计算next数组核心思想:找最长且小于串的公共前后缀,使得公共前缀滑动到公共后缀上 计算next数组时候无需看s(主串),只看t(模式串) 手写计算nextval时需要先...
  • next数组的作⽤:当模式串的第j个字符失配时,从模式串的第next[j]的继续往后匹配。 ①、任何模式串都一样,第一个字符不匹配时,只能匹配下一个子串,<font color='red'>next[1]都无脑写0 ②、任何模式串都一样,第...
  • KMP算法讲解(next数组求解)

    万次阅读 多人点赞 2019-05-12 16:27:05
    * 求待匹配串的next数组 */ void get_next_arr(char* t, int* next) { // next[i]的求解方法是,找到从t[0]~t[i-1]的公共最长匹配前缀和后缀的长度 next[0]=-1; // next[0]定义为-1 next[1]=0; // next[1]肯定是...
  • KMP算法的精髓在于next数组,首先解释next数组中的值代表的意义: eg:a b a c next【4】指在第四元素之前的三个元素中,前缀和后缀相同的最大长度为1+1=2, 所以next【4】=2; (关于前缀和后缀的问题,CSDN有很多...
  • KMP算法--求next数组

    2021-05-28 20:43:06
    最近在学数据结构,三天看了180页pdf,佩服我自己,当然最主要的还是我...next数组,我相信学过或者了解过KMP算法的对它一定不陌生,可以这样说,整个LMP算法的精髓就在于对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数组详解

    2019-07-26 15:40:00
    KMP算法的Next数组详解 引 开始 优化 KMP算法的Next数组详解 转载请注明来源,并包含相关链接。 引 网上有很多讲解KMP算法的博客,我就不浪费时间再写一份了。直接推荐一个当初我入门时看的博客吧: ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 616,187
精华内容 246,474
关键字:

Next数组