首页 > 试题广场 >

已知串 S= "babab ", 其 Next 数值序列为

[单选题]
已知串 S= "babab ", 其 Next 数值序列为
  • 01112
  • 01233
  • 01123
  • 01223
其实算这种next值,不用那么麻烦,我看过很多种算法,有的复杂的我都不想看,这里我把我的做法说一遍,相对简单点。
首先介绍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.
因此综合起来next值就是0 1 1 2 3,也就是答案C。
发表于 2017-09-15 11:15:40 回复(15)
Next数值序列需要计算字符串前缀和后缀最长匹配相同的长度加一而得。
第1位一定是0
看S第一位“b” ,没有前缀和后缀 所以一般第2位一定是1(0+1);
看S.substring(0,2)“ba” 前缀b后缀a,相等长度为0,第3位是1(0+1);
看S.substring(0,3)“bab” 前缀b=后缀b,相等长度为1,第4位是2(1+1);
看S.substring(0,4)“baba” 前缀ba=后缀ba,相等长度为2,第5位是3(2+1);

则S的Next数值序列为 01123
编辑于 2017-08-03 10:50:57 回复(0)
以下是个人理解:

比如上面那个:
(P)模式串 a b a a b c a c   
坐标:           1 2 3 4 5 6 7 8
next值            0 1 1 2 2 3 1 2   
坐标为1的a和坐标为2的b初始值就为0和1.
计算坐标为3的a的next值 ([]中的数字为坐标) :P[2] = b, next[2] = 1; P[next[2]] = P[1] = a;P[2] != P[1],所以next[3] = 1(好像是这么规定的?)
计算坐标为4的a的next值:P[3] = a, next[3] = 1; P[next[3]] = P[1] = a, next[next[3]] = next[1] = 1; P[3] = P[1],取匹配前的那个字母的前next的值(这个是坐标为3的a)+1得:next[4] =  next[next[3]] + 1 = next[1] +1 = 2;
计算坐标为5的b的next值:P[4] = a, next[4] = 2; P[next[4]] = P[2] = b, next[next[4]] = next[2] = 1; P[  next[ next[4] ]  ] = P[1] = a, next[   next[ next[4] ]  ] = 0。 取匹配前的那个字母的前next的值(这个是坐标为2的b)+1得:next[5] =  next[next[4]] + 1 = 2;
计算坐标为6的c的next值:P[5] = b, next[5] = 2; P[ next[5] ] = P[2] = b, next[ next[5] ] = 1;  取匹配前的那个字母的前next的值(这个是坐标为5的b)+1得:next[6] = 2 + 1 = 3;
...................
打字不易,如果有错误,万请指正!
如果觉得有用,麻烦点歌赞呗。
发表于 2017-06-14 22:25:02 回复(3)
首先看看next数组值的求解方法例如: 
模式串 a b a a b c a c 
next值 0 1 1 2 2 3 1 2 
       
       next数组的求解方法是:第一位的next值为0,第二位的next值为1,后面求解每一位的next值时,根据前一位进行比较。首先将前一位与其next值对应的内容进行比较,如果相等,则该位的next值就是前一位的next值加上1;如果不等,向前继续寻找next值对应的内容来与前一位进行比较,直到找到某个位上内容的next值对应的内容与前一位相等为止,则这个位对应的值加上1即为需求的next值;如果找到第一位都没有找到与前一位相等的内容,那么需求的位上的next值即为1。
       看起来很令人费解,利用上面的例子具体运算一遍。
       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值对应的值与第七位相同。
发表于 2017-06-13 23:02:52 回复(5)
1、KMP算法的核心就是next数组,有的也称为前缀表,作用就是,当模式串与主串不匹配时,指导模式串应该回退到哪个位置重新匹配。KMP相比于暴力求解,少做了无意义的比对(主串的指针是不用回退的),而是利用之前的比对结果,辅助模式串回退(遇到不匹配时),提高效率。
2、前缀表:前缀和后缀子串的最大长度。(前缀是指不包含尾字符的以第一个字符开头的所有子串,后缀是指不包含首字符的以最后一个字符结尾的所有子串)。后面会用实例解释。
3、next数组有多种定义,但实质是一样的,有的直接用前缀表,有的对前缀表做移位操作,有的对前缀表各位减1。至于牛客的这个答案。我们还是先求其前缀表。
// 前缀表
b--------------0    // 固定为0
ba-------------0    // 没有相等的前缀子串和后缀子串
bab------------1    // 前缀子串 b 和后缀子串 b 相等,故为1
baba-----------2    // 前缀子串 ba 和后缀子串 ba 相等,故为2 
babab----------3    // 前缀子串 bab 和后缀子串 bab 相等,故为3
4、本题答案所用的next数组,将上述前缀表右移一位,最前面补-1,最后各位再加1即可。即:
右移一位:   0 0 1 2 3 ----> 0 0 1 2
最前面补-1:   0 0 1 2 ----> -1 0 0 1 2
各位+1:   -1 0 0 1 2 ----> 0    1   1   2    3



编辑于 2020-10-06 21:14:20 回复(2)
编辑于 2020-03-06 20:22:03 回复(2)
元素的序号:12345 字母的序号:babab 求next数组 前两位为0,1 第三位:第三位的前一位是a,a对应的next下标为1,1的序号对应的为b,a与b不等,继续向前查找,找完也没有相同的,故next为1 第四位:第四位的前一位是b,b对应的next下标为1,序号为1对应的为b,b与b相等,故next为1+1=2 第五位:第五位前一位为a,a的对应next下标为2,序号2对应的为2,a与a相等,故next为2+1=3 综上:next为0,1,1,2,3 注意区分序号和next下标,自己手动已标出
编辑于 2019-07-30 21:47:29 回复(0)
搜了下百度,看懂下面的这个例子,就ok了:
模式串 P = 'abaabcac'的 next 函数值序列为01122312。
前两个字母next序列分别为01;
第三个"a"  时,它前一个字母为b,从头开始字母为a, a!=b所以为bai1;
第四个"a"  时,前字母为a,从头开始字母为a,a=a,所以值为1+1=2(相等时为串长加1);
第五个"b",前个字母为a,从头开始a,a=a,为2;
第六个"c",前个字母为b,再往前是a,ab,从头开始ab串,ab=ab,因此值为2+1=3;
第七个字母为"a",前个字母为c,与从头开始的第一个字母不相等,所以为1;
第八个为"c",前个字母为a,与开始第一个字母相等,因此为2。

发表于 2020-08-10 17:41:00 回复(0)
可以参考回文半径的理解方式
发表于 2020-02-05 18:08:08 回复(0)

求next找前后串相同的子串的最大长度,第一位个第二位是0 1

编辑于 2018-07-30 13:51:04 回复(0)
next数组求解方法: 首先第一位和第二位的next值为0和1,从第三位开始求next值时,判断前一位的字符与该字符的next值作为序号(这里假设序号为1)对应的字符是否相等,如果相等,当前位的next值为前一位的next值加上1;如果不相等,再把序号为1的字符对应的next值作为新的序号(假设这个新序号为3),把这个序号对应的字符和所求的当前位的前一位的字符进行比较(其实和前面的比较原理是一样的,只是更换了比较对象),如果相等,所求的当前字符对应的next值等于序号1对应的next值加上1(因为我们是用这个值作为新的序号,找到和前一位相等的字符),根据这个方法一直找下去,如果找不到,那当前位的next值为1。
发表于 2023-07-16 11:28:19 回复(0)
第i个值的next值=Max长度(前i项前缀,后缀相同子串)
发表于 2022-07-24 10:13:05 回复(0)
本身我是完全不懂这个的,刚刚百度了下算法,发现也还蛮简单了,没那么复杂呀。
babab      对应01???
从第三位开始要用算法:算法规则为:当前位的next值需要判断前位字符值:x是否等于其对应的next值所在的位的字符,以本题为例,第3位字符b的前一位字符为a,对应的next值为1,而第1位的字符为b,与前位字符a不相等,所以得往前一位,继续判断,前面无法完成判断了就默认为第3位字符b对应的的next值为1(默认规则),然后继续按照这种规则判断第4位,第四位字符为a,前位字符为b,next值为1,而第一位的字符为b,与前位字符b相等,第4位字符a对应的next值就等于当前进行判断字符对应的next值+1,即1+1=2,;接下来判断最后一位字符b,前位a/2,对应a,与前为a相等,所以最后一位字符b对应的next值为2+1=3,所以答案为01123.
再举个刚刚百度让我看懂的例子:已知串S= ‘ababaaababaa ’ , 求其 Next 数值序列
ababaaababaa                                                           对应01??????????
b/1 b!=a 默认1                                                            011???????
a/1 a=a   1+1=2                                                           0112??????
b/2 b=b  2+1=3                                                            01123?????
a/3 a=a   3+1=4                                                            011234????
a/4 a!=b   b/3 b!=a  a/1 a=a 1+1=2                             0112342???
a/2 b!=a   a/4 a!=b b/3....   a=a 1+1=2                        01123422??
b/2 b=b    2+1=3                                                          011234223?
a/3 a=a     3+1=4                                                          0112342234
这样算下来是不是很简单呢 
发表于 2021-03-20 13:58:55 回复(0)
一般next数组的第一位都是赋值为-1,所以按-1的方法来算,最后求出来的结果都每位都加1就可以了
发表于 2020-05-20 23:08:47 回复(0)