CSP-S 提高级 · CSP 2026 提高级第一轮 第 13 题

【单选】字符串 S = "ababaabab"，其所有既是真前缀又是真后缀的子串（非空）的长度之和是（ ）。

逐一比较 S 的前缀与后缀，找出所有既是真前缀又是真后缀（且非空）的子串：长度 2 的 "ab" 与长度 4 的 "abab"，长度和为 6。也可以用 KMP 的 next 数组沿失败链跳。

把 "ababaabab" 本身（长度 9）也算进"真前缀/真后缀"（真 = 不比原串长）；或者漏掉较短的 "ab"。

解析

本题考查字符串的前后缀（border）识别，也是 KMP 算法 next 数组的直接应用。

定义回顾

"既是真前缀又是真后缀的非空子串"称为 border（真前缀/真后缀 = 不等于原串本身）。

S = ababaabab（长度 9）

方法一：逐一比对

满足条件的长度是 2 和 4，长度之和 = 2 + 4 = 6，选 B。

方法二：KMP 的 next 数组（更快）

计算 S 的前缀函数 π（π[i] 表示前 i 个字符的最长 border 长度）：

π[9] = 4 → 最长 border 是 abab（长度 4）； 再沿失败链跳：π[4] = 2 → 下一个 border 是 ab（长度 2）； π[2] = 0 → 结束。

所有 border 长度：4, 2 → 和为 6 ✓

其他选项为什么错

• A. 4：只取了最长 border；
• D. 5、C. 7：把 aba、ababa 之类误判为 border（它们作为后缀时并不相同）。

记忆点

• "所有 border 的长度"可以用 KMP 的 π 数组沿 π[π[i]] 链条 O(n) 求出，这是 next 数组最常见的用途之一；
• 若题目问"所有 border 的总个数"，注意别把长度 0 或原串本身算进去；
• S 的 border 集合包含于"π 迭代链"：{π[9], π[π[9]], …}。