首页 > 试题广场 > 字符串′ababaabab′的nex
[单选题]
字符串′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)
推荐
     i       0    1    2    3    4    5    6    7    8
     s     a    b    a    b    a    a    b    a    b
next[i]  -1    0    0    1    2    3    1    2    3
先计算前缀next[i]的值:
next[i]的值主要是看s[i]之前的字符串中重复的子串长度。next[0] = -1,定值。  
next[1]是看s[1]之前的字符串“a”中重复的子串长度为0,故next[1] = 0。
next[2]是看s[2]之前的字符串“ab”中重复的子串长度为0,故next[2] = 0。
next[3]是看s[3]之前的字符串"aba"中重复的子串长度,s[0]与s[2]重复,长度为1,故next[3] = 1。
next[4]是看s[4]之前的字符串"abab"中重复的子串长度,s[01]与s[23]重复,长度为2,故next[4] = 2。
next[5]是看s[5]之前的字符串"ababa"中重复的子串长度,s[012]与s[234]重复,长度为3,故next[5] = 3。
next[6]是看s[6]之前的字符串"ababaa"中重复的子串长度,s[0]与s[5]重复(因为多了一个a,无法找到长度为3的重复字符串,这只能是s[0]和s[5]重复),长度为1,故next[6] = 1。
同样的,求next[7]和next[8]分别为2和3。
接下来计算nextval[i]的值:
nextval[i]的求解需要比较s中next[i]所在位置的字符是否与s[i]的字符一致,如果一致则用s[next[i]]的nextval的值作为nextval[i],如果不一致,则用next[i]做为nextval[i]。
nextval[0] = -1,和next[0]的值一样。
nextval[1],比较s[next[1]] ?= s[1],next[1] = 0,s[0] = a,而s[1] = b,二者不一致,则nextval[1] = next[1] = 0。
nextval[2],比较s[next[2]] ?= s[2],next[2] = 0,s[0] = a,而s[2] = a,二者一致,则nextval[2] = nextval[s[next[2]]] = nextval[s[0]] = -1(严谨来看这么表述是有问题的,因为nextval[2]表示nextval数组中 第3个数值,而nextval[s[0]]表示的是s[0]对应的字母‘a’所对应的nextval值 -1,这里nextval[]的用法并不严谨,只是为了表述方便 )。 
nextval[3],比较s[next[3]] ?= s[3],next[3] = 1,s[1] = b,而s[3] = b,二者一致,则nextval[3] = nextval[s[next[3]]] = nextval[s[1]] = 0。
nextval[4],比较s[next[4]] ?= s[4],next[4] = 2,s[2] = a,而s[4] = a,二者一致,则nextval[4] = nextval[s[next[4]]] = nextval[s[2]] = -1。
nextval[5],比较s[next[5]] ?= s[5],next[5] = 3,s[3] = b,而s[5] = a,二者不一致,则nextval[5] = next[5] = 3。
同样的求nextval[6],nextval[7],nextval[8]分别为 0 ,-1 , 0。
这里是nextval的下标从-1开始,如果从1开始,则其余各位均+1,nextval为0,1,0,1,0,4,1,0,1
编辑于 2016-03-04 13:27:24 回复(42)
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 回复(2)
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 回复(7)
看了老半天才明白怎么计算的,可以看看这个解析。
先计算出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 回复(3)

文章作者:姜南(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)
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)
模式串  a  b  a  a  b  c  a  c
next值  0  1  1  2  2  3  1  2
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值对应的值与第七位相同

求解nextval:

       求nextval数组值有两种方法,一种是不依赖next数组值直接用观察法求得,一种方法是根据next数组值进行推理,两种方法均可使用,视更喜欢哪种方法而定。
    本文主要分析nextval数组值的第二种方法:
  模式串      a b a a b c a c
  next值      0 1 1 2 2 3 1 2
  nextval值 0 1 0 2 1 3 0 2

  1.第一位的nextval值必定为0,第二位如果于第一位相同则为0,如果不同则为1。
  2.第三位的next值为1,那么将第三位和第一位进行比较,均为a,相同,则,第三位的nextval值为0。
  3.第四位的next值为2,那么将第四位和第二位进行比较,不同,则第四位的nextval值为其next值,为2。
  4.第五位的next值为2,那么将第五位和第二位进行比较,相同,第二位的next值为1,则继续将第二位与第一位进行比较,不同,则第五位的nextval值为第二位的next值,为1。
  5.第六位的next值为3,那么将第六位和第三位进行比较,不同,则第六位的nextval值为其next值,为3。
  6.第七位的next值为1,那么将第七位和第一位进行比较,相同,则第七位的nextval值为0。
  7.第八位的next值为2,那么将第八位和第二位进行比较,不同,则第八位的nextval值为其next值,为2。
发表于 2017-07-29 16:17:51 回复(0)
对于next还没搞懂。。nextval又是个什么啊。。。
发表于 2016-09-20 14:53:48 回复(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)
编辑于 2019-10-11 23:07:51 回复(0)
a
发表于 2019-05-01 16:54:37 回复(0)
public class Kmp {
    private static int[] getNextFromString(String s){
        int[] next=new int[s.length()];
        int p1=-1;
        int p2=0;
        next[0]=-1;
        while(p2<s.length()-1){
            while(p1!=-1&&s.charAt(p1)!=s.charAt(p2)) p1=next[p1];
            next[++p2]=++p1;
        }
        return next;
    }
    private static int[] getNextVal(String s,int [] next){
        int[] nextVal=new int[next.length];
        for(int i=0;i<next.length;i++){
            nextVal[i]=next[i];
            while(nextVal[i]!=-1&&s.charAt(nextVal[i])==s.charAt(i)) nextVal[i]=nextVal[nextVal[i]];
        }
        return nextVal;
    }
    private static void show(int[] a,int add){
        for(int aa:a){
            System.out.print(aa+add+" ");
        }
        System.out.println();
    }
    public static void main(String[] argv){
        String s="ababaabab";
        int add=1;//从1开始标记数组的下标
        int[] next=getNextFromString(s);
        show(next,add);
        int[] nextVal=getNextVal(s, next);
        show(nextVal,add);
    }
}
发表于 2018-11-07 18:11:58 回复(0)
你们去百度一下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)