首页 > 试题广场 > 串′ababaaababaa′的next数组为()
[单选题]
串′ababaaababaa′的next数组为()
  • 012345678999
  • 012121111212
  • 011234223456
  • 0123012322345

58个回答

添加回答
推荐
C
next数组的求解方
   查看全部
编辑于 2015-01-29 17:08:58 回复(14)
 答案也是借鉴大神的!只是拿来和大家分享!!! 
     i       0    1    2    3    4    5   6   7    8   9   10  11
     s     a    b    a    b    a    a   a   b    a    b   a    a  
next[i]   -1   0    0   1     2    3   1   1    2    3   4    5
先计算前缀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]、next[9]、 next[10]、 next[11] 分别为1和2、3、4、5。
发表于 2016-03-02 15:38:50 回复(35)
next数组下标从1开始计算
next[1] 肯定是 0 
next[2] 肯定是 1
next[n] 的情况,将前面n-1个字符,计算从首尾开始组成最大的相同子串的长度,如果找到,那么next值是该长度加1,否则next值是1。

举例
next[6]的计算,字符串第六位是 a ,( ababa a ababaa)
将前面的5个字符,从头尾开始取4个组成子串比较,如果不相等,则从首尾取3个字符组成子串继续比较,并以此类推, 如果一直比较到最后一个字符都不相等,那么该next值为1。
4个字符的情况:abab : baba
3个字符的情况:aba   :  aba  此时相等,那么next[6] = 3+1 = 4



编辑于 2015-08-11 10:56:46 回复(18)
KMP算法的部分匹配值问题。
- "a"的前缀和后缀都为空集,共有元素的长度为0;

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

- "aba"的前缀为[a, ab],后缀为[ba, a],共有元素的长度1;

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

- "ababa"的前缀为[a, ab, aba, abab],后缀为[baba, aba, ba, a],共有元素为"aba",长度为3;
以此类推,00123等

发表于 2015-09-02 19:50:12 回复(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值对应的值与第七位相同。
发表于 2016-05-07 22:13:09 回复(1)
发表于 2018-02-07 22:44:12 回复(0)
刚好总结了一下next数组求解,可归纳为“三角形法”,原理如下:
举个简单的例子:串 “a b a a b c a c ”,
计算第五位(蓝色线标记)的时候,看第四位a的next值,为2,则把a和2对应的b进行比较,不同;(第一个三角形)
再将b对应的next值1对应的a与第四位的a进行比较,相同;(第二个三角形)
则第五位的next值为第二位b的next值加上1,为2。因为是在第二位实现了其next值对应的值与第四位的值相同。
同理可在′ababaaababaa′字符串上操练,结果为011234223456
其余值的详细求法看这里: http://blog.csdn.net/quitepig/article/details/7933977 
编辑于 2016-03-11 19:38:50 回复(0)
正确答案应该是:
001231123456

发表于 2015-04-09 20:29:48 回复(7)

先给出答案:

计算过程:

next数组值的计算依据下面的分段函数

最大k值代表当模式中第j个字符与主串中第i个字符“失配”时,在该模式串中需要重新和主串中第i个字符进行比较的字符位置,最大k值与最终求得的next[j]值是相等的

一定要注意观察分段函数第二段求max[k]时的满足条件,模式串中的最大相同子串应该满足:

所以k值很关键,要找到一个最大k值,满足上式。

它是根据下面这张图片推出来的,假设主串为S1S2···Sn,模式串为P1P2···Pm,此时图片中对应的情形是主串中第i个字符与模式中第j个字符“失配”

下面结合这道题具体分析:

发表于 2017-07-18 16:54:03 回复(1)
next数组下标从1开始计算
next[1] 肯定是 0 
next[2] 肯定是 1
next[n] 的情况,将前面n-1个字符,计算从首尾开始组成最大的相同子串的长度,如果找到,那么next值是该长度加1,否则next值是1。

举例
next[6]的计算,字符串第六位是 a ,( ababa a ababaa)
将前面的5个字符,从头尾开始取4个组成子串比较,如果不相等,则从首尾取3个字符组成子串继续比较,并以此类推,如果一直比较到最后一个字符都不相等,那么该next值为1。
4个字符的情况:abab : baba
3个字符的情况:aba   :  aba  此时相等,那么next[6] = 3+1 = 4

发表于 2015-09-17 11:30:24 回复(3)
按照kmp思路,最大长度表为001231123456则对应的next数组为-100123112345,由答案可知,此题中是从下标1开始,所以可推倒答案为
011234223456
编辑于 2015-10-02 12:02:04 回复(0)
看到这种题目我选择狗带
发表于 2015-09-23 16:28:47 回复(0)
编辑于 2016-06-18 15:48:36 回复(4)

我的结果是001231123456,不知道答案这个是怎么算出来的,求解释啊

编辑于 2016-04-29 13:48:08 回复(0)
翻阅各种资料整理的结论是:
                              a b a b a a a b a b a a
KMP部分匹配表:0 0 1 2 3 1 1 2 3 4 5 6
           next数组 :0 1 1 2 3 4 2 2 3 4 5 6

所以,有没有大神解答一下我的疑惑:到底部分匹配表表示匹配长度,next数组的用意表示什么呢? 
发表于 2015-11-19 18:00:45 回复(0)

KMP算法是字符串模式匹配的一个改进的算法,此算法可以 在O(m+n)的时间数量级上完成串的模式匹配操作。其主要是求next[]数组。我的这个见解只为了很快求出next[]数组,至于具体的代码实现,还是用经典的代码实现。

KMP算法的思想是当主串中的第i个字符与模式中的第j个字符“失配“(即比较不相等)时,主串中的第i个字符(i不回溯,当然是可以往前加1的)应与模式中的哪个字符比较。(这个可以先不理解,看完就懂啦)

举个例子:

j 1 2 3 4 5 6 7 8
模式串 a b a a b c a c
next[j] 0 1 1 2 2 3 1 2


next[j]就是找到p1p2......pj-1这个串中”最长的对称的字符串“。我是加引号的啊,不一定是你想的对称啊!

个人思想:

next[1]为0,next[2]为1,这是不用再算的,也是一定的。我们也没有必要再费心去算。我们从第三个开始。

 aba: 其前缀字符串是ab.我们所说的最长的对称子字符串是指这样的对称。如:ab  ab 。而不是类似这样的对称,

ab  ab  a。对,我想表达的意思就是第一个字符串中必须含有第一个字符,第二个字符串中必须含有最后一个字符。所以ab的最长的对称的字符串是0,所以我们的next[3]=0+1=1,对就是最长字符串加1。至于为什么是这样,我想表达一下,却发现很难用语言来说明(原谅我吧)

abaa:其前缀字符串是aba,按我们所说的对称标准,其最长的对称字符串的长度是1,所以其next[4]=1+1=2。

abaab:其前缀字符串是abaa,其最长的对称字符串长度也是1,所以其next[5]=1+1=2;

abaabc:其前缀字符串是abaab,其最长的对称字符串是前后的ab,所以其长度是2,所以next[6]=2+1=3;

abaabca:其前缀字符串是abaabc,是没有我们所说的对称的,所以是0,所以next[7]=0+1=1.注意:这里的p1p2=ab,p4p5=ab,这两个字符串不是我们所要的对称字符串。因为第二个字符串没有包含p6,即pj-1这个字符。

。。。。。。。。。。。。。

发表于 2015-11-16 23:05:53 回复(1)
这个next数组不应该是一个主串一个子串两个拿来进行比较吗?不是很明白这个题的意思,如果是匹配字符串的话,直接next函数就可以了啊
next[j]=-1(当j=0时)
next[j]=max(k)   (1<=k<j&&T[0]...T[k-1]=T[j-k]....T[j-1],满足此条件的最大的K值)
next[j]=0   (other)
发表于 2018-07-11 20:48:15 回复(0)
这里的next数组不是KMP里的next(),可以参考我转载的博文
编辑于 2018-05-08 17:53:02 回复(0)
(1)计算前缀后缀的最大公共元素长度 
(2)最大公共元素长度整体右移一位,第一个元素值填 -1,即为 next 数组的第一版本 
(3)(如果你需要的 next 数组第一个值为 -1,这步就可以省略了)next 数组的每一个值分别+1,即求得 next 数组。
发表于 2018-01-26 15:49:39 回复(0)
C  只看下前几个就可以确定答案了
发表于 2015-09-13 12:28:08 回复(0)
编辑于 2015-08-15 09:08:11 回复(0)

扫一扫,把题目装进口袋

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

扫描二维码,进入QQ群

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

  • 公司地址:北京市朝阳区大屯路东金泉时代3-2708北京牛客科技有限公司
  • 联系方式:010-60728802(电话) admin@nowcoder.com
  • 牛客科技©2018 All rights reserved
  • 京ICP备14055008号-4
  • 京公网安备 11010502036488号