题7

题7

题目

串’ababaaababaa’ 的 next 数组值为 ( ).
A. 01234567899
B. 012121111212
C. 011234223456
D. 0123012322345

分析

这道题采用手工求 next 数组的方法。先求串 S = 'ababaaababaa' 的部分匹配值:

• ‘a’ 的前后缀都为空, 最长相等前后缀长度为 0 。
• ‘ab’ 的前缀 { a } ∩ 后缀 { b } = ∅, 最长相等前后缀长度为 0 。
• ‘aba’ 的前缀 { a, {ab} } ∩ 后缀 { a, {ba} } = { a }, 最长相等前后缀长度为 1 。
• ‘abab’ 的前缀 { a, {ab}, {aba} } ∩ 后缀 { b, {ab}, {bab} } = { {ab} }, 最长相等前后缀长度为 2 。
  依次求出的部分匹配值见下表第 3 行, 将其整体右移一位, 低位用 -1 填充, 见下表第 4 行。

编号	1	2	3	4	5	6	7	8	9	10	11	12
S	a	b	a	b	a	a	a	b	a	b	a	a
PM	0	0	1	2	3	1	1	2	3	4	5	6
next	-1	0	0	1	2	3	1	1	2	3	4	5

选项中 `next[1]` 等于 0, 所以将 `next` 数组整体加 1 。 ### 解 C