CSP-S 2025 第一轮 第2题：在 KMP 算法中，对于模式串 P = \tt{abacaba}，其 next

题目

在 KMP 算法中，对于模式串 $P = \tt{abacaba}$，其 next 数组（next[i] 定义为模式串 $P[0..i]$ 最长公共前后缀的长度，且数组下标从 0 开始）的值是什么？

选项

• A. $\{0, 0, 1, 0, 1, 2, 3\}$
• B. $\{0, 1, 2, 3, 4, 5, 6\}$
• C. $\{0, 0, 1, 1, 2, 2, 3\}$
• D. $\{0, 0, 0, 0, 1, 2, 3\}$

答案

A

题解

答案是 A：$\{0,0,1,0,1,2,3\}$。

按题目定义，next[i] 是子串 $P[0..i]$ 的最长相等真前缀、真后缀的长度。“真”表示不能包含整个子串，否则前后缀永远是它本身。

逐个计算：

例如，abacaba 的开头和结尾都是 aba，且不存在更长的相等真前后缀，所以最后一项是 3。

注意：KMP 的 next 数组有不同定义，做题时应以题目给出的定义为准。