CSP-S 提高级 · CSP 2025 提高级第一轮 第 2 题

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

这题就是考 KMP 里 next 数组的原始定义。拿到串先别急着套代码，从长度 1 开始，一位一位加，看能不能在刚才找到的最长公共前后缀基础上再往前多拼一个字符；拼不上就回退到前一位的 next 值继续找，直到拼成或回退到 0。

最容易栽跟头的就是把 next 和 prefix 数组搞混。prefix[i] 通常存的是 P[0..i] 最长公共前后缀长度，而题目明确说 next[i] 就是这个值，但很多同学习惯用 KMP 代码里那种 next[i] 表示 P[0..i-1] 的 LCP，导致算出来的数组整体右移一位。另外，计算时往往忘记“不能是字符串本身”这个限制，把整个串当成前后缀，或者在回退时没有正确利用前一位的 next 值，直接重新从头找，这样就会多算或少算，比如把 P[3] 算成 1 而不是 0。

考察知识点

字符串算法 — KMP 算法

概念定义

• KMP 算法：一种高效的字符串匹配算法，核心在于预处理模式串得到一个 next 数组，从而将匹配过程优化到线性复杂度。
• next 数组（本题定义）：next[i] 表示模式串 P[0..i] 的最长公共前后缀（LCP）的长度。

- 前缀：从第一个字符开始连续的子串。 - 后缀：以最后一个字符结束连续的子串。 - 公共前后缀：既是前缀又是后缀的子串，且长度必须小于子串本身（不能是整个串）。例如 "aba" 的前缀有 a, ab, aba；后缀有 a, ba, aba；公共的是 a（长度 1）。

命题视角

命题人喜欢考这种“定义陷阱”。KMP 的 next 数组在教材和代码实现中有多种变体（有的从 1 开始，有的存的是前一位的 LCP），但本题白纸黑字给出了定义：next[i] 就是 P[0..i] 的 LCP 长度。这意味着我们不需要记忆代码里的具体写法，只需要按定义手工模拟即可。这类题往往出现在单选里，目的是考察你对概念本质的理解，而不是对某段特定代码的背诵。

思考心法

拿到题先想什么？ 1. 逐位推进：从 i=0 开始，一位一位地往右看。 2. 尝试扩展：假设 P[0..i-1] 的 LCP 长度是 k，那么 P[0..k-1] 就是当前的候选前后缀。检查 P[k] 是否等于 P[i]。如果相等，说明我们可以把长度加 1，即 next[i] = k+1。 3. 回退机制：如果不相等，说明当前的 k 太大了，需要缩小。怎么缩？直接跳到 next[k-1] 对应的长度再试。因为 next[k-1] 已经是 P[0..k-1] 的最长公共前后缀长度，它对应的子串肯定也是 P[0..k] 的前缀，我们只需检查 P[next[k-1]] 是否等于 P[i]。 4. 兜底：如果回退到 0 还是不等，那 next[i] 就是 0。

具体计算（P = abacaba）

• i = 0：串 "a"，长度 1，没有真前后缀 → next[0] = 0。
• i = 1：串 "ab"，前缀 a，后缀 b，不等 → next[1] = 0。
• i = 2：串 "aba"，前缀 a，后缀 a，相等 → next[2] = 1。
• i = 3：串 "abac"，前缀 a，后缀 c，不等；回退到 next[1]=0，串 "a"，后缀 c，仍不等 → next[3] = 0。
• i = 4：串 "abaca"，前缀 a，后缀 a，相等 → next[4] = 1。
• i = 5：串 "abacab"，前缀 ab，后缀 ab，相等 → next[5] = 2。
• i = 6：串 "abacaba"，前缀 aba，后缀 aba，相等 → next[6] = 3。

得到数组：{0, 0, 1, 0, 1, 2, 3}。

避坑指南

• 别把答案右移：选项 A 是 {0, 0, 0, 1, 0, 1, 2, 3}，多了一个前导 0，这是某些实现里 next[0] 被定义为 0 且数组长度多一位的写法，但本题明确下标从 0 开始且只到 i=6，所以正确答案就是 7 个元素的 {0, 0, 1, 0, 1, 2, 3}。选项 C 和 D 把 next[2] 或 next[3] 算错了，说明要么没回退，要么把整个串当成前后缀了。
• 记住“不能是本身”：比如 "aa" 的公共前后缀是 a（长度 1），不是 aa（长度 2）。

考频与趋势

• 字符串算法：题库共考过 7 题，覆盖 2 个考试级别（2019-2025）；逐年分布：2019 年 1 题、2020 年 1 题、2022 年 1 题、2023 年 1 题、2025 年 3 题；分赛事：CSP 提高级 5 题、CSP 入门级 2 题。
• KMP 算法：题库共考过 2 题，覆盖 1 个考试级别（2022-2025）；逐年分布：2022 年 1 题、2025 年 1 题；分赛事：CSP 提高级 2 题。

从数据看，KMP 在 CSP 提高级里属于低频但稳定的考点，2025 年已经连续两年出现，且 2025 年字符串算法整体爆发（3 题），说明命题人正在加大字符串相关内容的比重。

预测

基于现有数据，KMP 在 CSP 提高级中未来 1-2 年内仍有一定概率出现，但大概率会保持低频（每年 0-1 题）。不过，既然 2025 年字符串算法题量明显上升，命题趋势显示字符串类题目正在升温，因此 KMP 或其变体（如 Z 函数、Manacher）在未来考试中出现的概率会略微提高。暂无足够依据预测具体年份和题量，但建议复习时把 KMP 的多种 next 定义版本都过一遍，以防命题人换个马甲再来考。