首页 > 试题广场 > 字符串′ababaabab′的nextval为()
[单选题]
字符串′ababaabab′的nextval为()
  • (0,1,0,1,0,4,1,0,1)
  • (0,1,0,1,0,2,1,0,1)
  • (0,1,0,1,0,0,0,1,1)
  • (0,1,0,1,0,1,0,1,1)

45个回答

添加回答
推荐
     i       0
   查看全部
编辑于 2016-03-04 13:27:24 回复(40)
ref: http://www.slyar.com/blog/kmp-next-nextval.html
i    0  1  2  3  4  5  6  7  8
s    a  b  a  b  a  a  b  a  b
next  -1  0  0  1  2  3  1  2  3

nextval[0] = -1;
s[1]=b != s[next[1]]=s[0]=a; nextval[1]=next[1]=0;
s[2]=a = s[next[2]]=s[0]=a, nextval[2]=nextval[0]=-1;
s[3]=b = s[next[3]]=s[1]=b, nextval[3]=nextval[1]0;
s[4]=a = s[next[4]]=s[2]=a, nextval[4]=nextval[2]=-1;
s[5]=a != s[next[5]]=s[3]=b, nextval[5]=next[5]=3;
s[6]=b = s[next[6]]=s[1]=b, nextval[6]=nextval[1]=0;
s[7]=a = s[next[7]]=s[2]=a, nextval[7]=nextval[2]=-1;
s[8]=b = s[next[8]]=s[3]=b, nextval[8]=nextval[3]=0;

nextval -1 0 -1 0 -1 3 0 -1 0

有的时候下标从1开始即 0 1 0 1 0 4 1 0 1
发表于 2015-03-12 21:13:38 回复(1)
i            1 2 3 4 5 6 7 8 9
s           a b a b a a b a b
next      0 1 1 2 3 4 2 3 4
nextval 0 1 0 1 0 4 1 0 1


发表于 2015-09-04 14:36:25 回复(5)

文章作者:姜南(Slyar) 文章来源:Slyar Home (www.slyar.com) 转载请注明,谢谢合作。

KMP 算法我们有写好的函数帮我们计算 Next 数组的值和 Nextval 数组的值,但是如果是考试,那就只能自己来手算这两个数组了,这里分享一下我的计算方法吧。

计算前缀 Next[i] 的值:

我们令 next[0] = -1 。从 next[1] 开始,每求一个字符的 next 值,就看它前面是否有一个最长的"字符串"和从第一个字符开始的"字符串"相等(需要注意的是,这2个"字符串"不能是同一个"字符串")。如果一个都没有,这个字符的 next 值就是0;如果有,就看它有多长,这个字符的 next 值就是它的长度。

计算修正后的 Nextval[i] 值:

我们令 nextval[0] = -1。从 nextval[1] 开始,如果某位(字符)与它 next 值指向的位(字符)相同,则该位的 nextval 值就是指向位的 nextval 值(nextval[i] = nextval[ next[i] ]);如果不同,则该位的 nextval 值就是它自己的 next 值(nextvalue[i] = next[i])。

举个例子:

手算kmp的next和nextval

计算前缀 Next[i] 的值:

next[0] = -1;定值。
next[1] = 0;s[1]前面没有重复子串。
next[2] = 0;s[2]前面没有重复子串。
next[3] = 0;s[3]前面没有重复子串。
next[4] = 1;s[4]前面有重复子串s[0] = 'a'和s[3] = 'a'。
next[5] = 2;s[5]前面有重复子串s[01] = 'ab'和s[34] = 'ab'。
next[6] = 3;s[6]前面有重复子串s[012] = 'abc'和s[345] = 'abc'。
next[7] = 4;s[7]前面有重复子串s[0123] = 'abca'和s[3456] = 'abca'。

计算修正后的 Nextval[i] 值:

nextval[0] = -1;定值。
nextval[1] = 0;s[1] != s[0],nextval[1] = next[1] = 0。
nextval[2] = 0;s[2] != s[0],nextval[2] = next[2] = 0。
nextval[3] = -1;s[3] == s[0],nextval[3] = nextval[0] = -1。
nextval[4] = 0;s[4] == s[1],nextval[4] = nextval[1] = 0。
nextval[5] = 0;s[5] == s[2],nextval[5] = nextval[2] = 0。
nextval[6] = -1;s[6] == s[3],nextval[6] = nextval[3] = -1。
nextval[7] = 4;s[7] != s[4],nextval[7] = next[7] = 4。

发表于 2016-03-21 16:00:34 回复(5)
看了老半天才明白怎么计算的,可以看看这个解析。
先计算出next数组,然后要计算当前位置的nexteval,就将当前的字符与当前位置的next指向的字符比较,如果相等,那么这个nexteval就是前面那个的nexteval值,不等,那就是等于next值。
i              1 2 3 4 5 6 7 8 9
s             a b a b a a b a b
next        0 1 1 2 3 4 2 3 4
nexteval  0 1 0 1 0 4 1 0 1
第一个的nexteval为 0
第二个的next为1,但是位置1的是a, a!=b,所以nexteval[2] = next[2]。
第三个的next为1,位置1为a, a == a,所以nexteval[3] = nexteval[1]
第四个的next为2,位置2为b, b == b,所以nexteval[4] = nexteval[2]
依次类推就可以了
编辑于 2016-05-04 22:57:45 回复(1)
if src[i]==src[next[i]]
    nextval[i]=nextval[next[i]];
else
    nextval[i]=next[i];

发表于 2015-08-19 12:09:03 回复(0)
http://kb.cnblogs.com/page/176818/
看完这篇文章一定能懂
发表于 2016-03-10 09:44:04 回复(2)


编辑于 2018-08-30 15:59:36 回复(0)
i            1 2 3 4 5 6 7 8 9
s           a b a b a a b a b
next      0 1 1 2 3 4 2 3 4
nextval 0 1 0 1 0 4 1 0 1
next值可求出,然后求Nextval,第几位就和哪一位的值比较,如果和那一位的值相同,就把它copy下来,如果不是,就是自己的Next值不变,例如第三位:为1和第一位比较,也是a,就把它的值0记录下来,第六位与第四位相比不同,为第六位本来的值,为4.
发表于 2016-03-07 22:05:19 回复(2)
碧海浮云新浪博客:http://blog.sina.com.cn/s/blog_4dc87a56010009oz.html
n    1    2    3    4    5    6    7    8    9
s    a    b    a    b    a    a    b    a    b
nx   0   1    1    2    3    4    2    3    4
nxv 0    1     0     1     0     4     1     0     1
发表于 2015-07-15 15:58:03 回复(1)
你们去百度一下nextval 然后会发现那些博客说的跟这里的解释完全不一样 晕 我都不知道谁是对的 连开头next 1 2的固定值都不一样 醉了 你们到底会不会啊
发表于 2018-10-08 11:06:35 回复(0)
😞KMP学的时候没学懂,现在还是没学懂
发表于 2018-09-04 10:11:12 回复(0)
发表于 2018-08-19 15:55:01 回复(0)
上面解析没有看懂的朋友可以参照这个:
最后补充一句:链接2中是从-1开始的,若从0开始则所有数值都加1
发表于 2018-07-23 15:24:20 回复(0)
很详细
发表于 2018-05-24 23:30:53 回复(0)

一般情况下,想要算nextval就必须先把next数组算出来。next数组是(0,1,1,2,3,4,2,3,4)

现在开始算nextval数组

1.      第一位必定是0

2.      第二位的b,对应next值1,查看b和第1位的a不相等,继承自己的next值=1。

3.      第三位的a,对应next值1,查看a和第1位的a发现相等,继承第一位a的nextval=0

4.      第四位的b,对应的next值为2,查看b和第2位的b发现相等,继承第二位b的nextval=1

5.      第五位的a,对应的next值为3,查看a和第3位a发现相等,继承第三位a的nextval=0

6.      第六位的a,对应的next值为4,查看a和第4位b发现不等,继承自己的next值=4

7.      第七位的b,对应的next值为2,查看b和第2位b发现相等,继承nextval值=1

8.      第八位的a,对应的next值为3,查看a和第3位a发现相等,继承nextval值=0

9.      第九位的b,对应的next值为4,查看b和第4位b发现相等,继承nextval=1

综上,最后结果为(0,1,0,1,0,4,1,0,1
发表于 2018-05-06 09:26:07 回复(0)
nextval不要看成next
发表于 2018-04-28 18:11:21 回复(0)

next[i] 计算方法

前提:pattern字符index从1开始

1.除去第i个字符,得到前面i-1个字符。

2.第一个字符next值定义为0

3.从i-1各字符的 第一个 和 最后一个 分别向中间找,找出最长的相同子串。

特例:aaab中b之前字符串aaa的最长子串是aa!

4.子串长度为 l ,则next值为 l+1.
nextval[i] 计算方法
next指示的位置如果与pattern当前失配字符相同,则必然再次失配,此时会链式地回到最初相同字符的next值,则应将这些next值置为最初的值。
发表于 2018-04-11 11:20:49 回复(0)
不就是一个改进的KMP么,推荐答案既不是编程逻辑,又不是直观解释,写一堆对别人没有任何帮助的话有啥意义么?这样都是推荐答案我也是醉了
发表于 2018-04-07 10:32:15 回复(0)
这个是拿来干啥的?
发表于 2018-03-28 00:15:17 回复(0)
推荐答案。新手小白说得很棒了,不过求nextval那里说得很绕,我补充下我的理解。 …………………………………………………… nextval求法,只需要判断s[next[i]]和s[i]即可 1.不等:nextval[i] = next[i] 2.相等:nextval[i] = nextval[ next[i] ] 对s=ababaabab易求得next[]为 -1 0 0 1 2 3 1 2 3 初始值nextval[0] = -1(下面序号k代表求nextval[k]的值) 1. s[0]=a s[1]=b,不等,next[1]: 0 2. s[0]=a s[2]=a,相等,nextval[0]: -1 3. s[1]=b s[3]=b,相等,nextval[1]: 0 4. s[2]=a s[4]=a,相等,nextval[2]: -1 5. s[3]=b s[5]=a,不等,next[5]: 3 6. s[1]=b s[6]=b,相等,nextval[1]: 0 7. s[2]=a s[7]=a,相等,nextval[2]: -1 8. s[3]=b s[8]=b,相等,nextval[3]: 0 综上,结果是-1 0 -1 0 -1 3 0 -1 0 把所有数加1即可,结果为 0 1 0 1 0 4 1 0 1 …………………………………………………… 虽然我根本不知道nextval到底是什么东西,从应试的角度就这样吧。
发表于 2018-02-26 01:10:22 回复(0)

扫一扫,把题目装进口袋

牛客网,程序员必备求职神器

扫描二维码,进入QQ群

扫描二维码,关注牛客网公众号