我要招人

去企业版

首页 > 试题广场 >

字符串 "ababaaababaa" 的 next 数组为（

[单选题]

字符串 "ababaaababaa" 的 next 数组为（）

```
012345678999
```
```
012121111212
```
```
011234223456
```
```
012301232234
```

推荐

1——1

next[1] = 0

next[2] = 1

（这两个值是约定的）

next[3]: "ab"没有相同的前缀和后缀，所以模式串又得从头开始匹配，因此next[3] = 1

next[4]: "aba"的最长公共串是“a”，所以按照下面这个例子，虽然第四位没有匹配上，但是前三位匹配上了，并且第一位和第三位相同，因此可以将模式串整体向右移动，直到将原来的第一位移到原来的第三位上，继续进行匹配，而原来模式串指针指着的第四位现在指向第二位了，因此next[4] = 2

abacfffffffffff...

ababaaababaa

ababaaababaa

next[5]: "abab"的最长公共串是“ab”，next[5] = 3

ababcfffffff...

ababaaababaa

ababaaababaa

next[6]: "ababa"最长公共串是“aba”，next[6] = 4

ababacfffffff...

ababaaababaa

ababaaababaa

next[7]: "ababaa"最长公共串是“a”，next[7] = 2

ababaacffffff...

ababaaababaa

ababaaababaa

next[8]: "ababaaa"最长公共串是“a”，next[8] = 2

next[9]: "ababaaab"最长公共串是“ab”，next[9] = 3

next[10]: "ababaaaba"最长公共串是“aba”，next[10] = 4

next[11]: "ababaaabab"最长公共串是“abab”，next[11] = 5

next[12]: "ababaaababa"最长公共串是“ababa”，next[12] = 6

next数组为

编辑于 2019-05-21 20:39:37 回复(4)

马到福来

发表于 2019-01-15 16:16:56 回复(14)

Jiang锋

	1	2	3	4	5	6	7	8	9	10	12	12
	a	b	a	b	a	a	a	b	a	b	a	a
maxl	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

所以选C

发表于 2018-11-11 14:21:43 回复(2)

小y虫-周伯通

字符串 "ababaaababaa" 的 next 数组为（）
next(1) 0
next(2) a 0+1=1
next(3) ab 0+1=1
next(4) aba 前缀 a,ab 后缀 a,ba 1+1=2
next(5) abab 前缀 a,ab,aba 后缀 b,ab,bab 2+1=3
next(6) ababa 前缀 a,ab,aba,abab 后缀 a,ba,aba,baba 3+1=4
next(7) ababaa 前缀 a,ab,aba,abab,ababa 后缀 a,aa,baa,abaa,babaa 1+1=2
next(8) ababaaa 前缀 a,ab,aba,abab,ababa,ababaa 后缀 a,aa,aaa,baaa,abaaa,babaaa 1+1=2
next(9) ababaaab 前缀 a,ab,aba,abab,ababa,ababaa,ababaaa 后缀 b,ab,aab,aaab,baaab,abaaab,babaaab 2+1=3
next(10)ababaaaba 前缀 a,ab,aba,abab,ababa,ababaa,ababaaa,ababaaab 后缀 a,ba,aba,aaba,aaaba,baaaba,abaaaba,babaaaba 3+1=4
next(11)ababaaabab 前缀 a,ab,aba,abab,ababa,ababaa,ababaaa,ababaaab,ababaaaba 后缀 b,ab,bab,abab,aabab,aaabab,baaabab,abaaabab,babaaabab 4+1=5
next(12)ababaaababa 前缀 a,ab,aba,abab,ababa,ababaa,ababaaa,ababaaab,ababaaaba,ababaaabab 后缀 a,ba,aba,baba,ababa,aababa,aaababa,baaababa,abaaababa,babaaababa 5+1=6
所以 011234223456

发表于 2022-04-06 17:30:49 回复(0)

新玥

求next数组：1.以0开头。下标从1开始，next[i]对应于x的第i位。初始化置next[1]＝0,next[2]＝1. 对于next[i]计算前i-1个字符的子串的前后缀公共长度，然后加1。 2. 以-1开头。对应位计算前后缀公共长度，然后右移一位，左边添-1。

编辑于 2018-09-28 08:39:50 回复(0)

为你扣下F键

next数组有两种，一种是next[0]=0的，还有一种是next[0]=-1的

编辑于 2018-08-08 22:04:04 回复(0)

牛客3711266号

根据KMP算法中next数组的计算方法，即可得出答案。

编辑于 2019-05-21 20:39:07 回复(3)

帅的我该怎么办

https://blog.csdn.net/wenyun_kang/article/details/65436838?locationNum=13&fps=1

发表于 2018-08-08 11:02:47 回复(0)

牛客561402624号

我们能确定next数组第一二位一定分别为0，1，后面求解每一位的next值时，根据前一位进行比较。从第三位开始，将前一位与其next值对应的内容进行比较，如果相等，则该位的next值就是前一位的next值加上1；如果不等，向前继续寻找next值对应的内容来与前一位进行比较，直到找到某个位上内容的next值对应的内容与前一位相等为止，则这个位对应的next值加上1即为需求的next值；如果找到第一位都没有找到与前一位相等的内容，那么求解的位上的next值为1。

发表于 2022-04-25 16:57:51 回复(0)