NOIP 提高组初赛 · NOIP 2008 提高组初赛试题 第 3 题

设字符串 $S= \texttt{Olympic}$，$S$ 的非空子串的数目是（ ）。

这题考字符串子串计数。拿到题先别急着套公式，先数清串长 n=7，再想子串长度从 1 到 n 每种长度各有多少个，最后求和。

最容易掉进两个坑：一是只数长度 1 的子串忘了后面还有更长的，比如有人只答 7 个选 E；二是把子串当成子序列去数组合数 C(7,2)，或者误以为子串必须连续且不重复，导致把答案算成 16 或 17 选 C/D。记住子串定义是连续片段，长度 1 的有 7 个，长度 2 的有 6 个……依次递减，千万别漏掉任何一项。

考点与概念

这题考查的是字符串中“子串”的基本计数能力。子串的定义很简单：原串中连续的一段字符。比如"Olympic"里，"O""Ol""Oly"…都是子串。题目问的是“非空子串”，也就是长度至少为 1 的所有子串总数。

命题视角

命题人喜欢用这种纯计算题来检验学生是否真正理解“子串”和“子序列”的区别，以及是否掌握求和公式。这类题通常不会涉及复杂的算法，但容易因为粗心或概念混淆选错。它常出现在初赛的基础语法部分，用来拉开基础与熟练的差距。

思考心法

拿到题，第一步是确认串长 n=7。第二步，按长度分类：

• 长度为 1 的子串：每个字符单独成串，共 7 个；
• 长度为 2 的子串：从第 1 个字符开始取 2 个，到第 6 个字符开始取 2 个，共 6 个；
• 长度为 3 的子串：共 5 个；
• ……
• 长度为 7 的子串：只有整个串本身，共 1 个。

第三步，把这些数量加起来：7+6+5+4+3+2+1。这就是一个等差数列求和，公式是 n(n+1)/2。

具体计算

代入 n=7： 7+6+5+4+3+2+1 = 28

或者直接用公式：7×8÷2 = 28。

避坑提醒

• 别把子串当成子序列：子序列可以不连续，数量会远大于 28，常见错误是算成 C(7,2)=21 或 28 以外的数字。
• 别漏掉长度 1 的子串：有人以为“子串”至少两个字符，结果只数了后面 6+5+…+1=21 个，选了 A 或 C。
• 别重复计数：子串是按起始位置和长度唯一确定的，不会有多余的重复。

考频与趋势

从题库统计看，字符串基础语法在 1295 题中占比不小，历年分布为：2008 年 1 题、2011 年 1 题、2019 年 3 题、2023 年 287 题、2024 年 413 题、2025 年 401 题、2026 年 109 题、null 年 80 题。分赛事来看，GESP 一级考了 332 题，二级 283 题，三级 215 题，四级 186 题，七级 91 题，八级 79 题，六级 78 题，五级 23 题；CSP 提高级和入门级各 3 题，NOIP 提高组初赛考了 2 题。

数据表明，字符串子串计数属于高频考点，尤其在 GESP 一级到四级中反复出现，说明命题人认为这是必须掌握的基础技能。近三年来（2023-2025）这类题数量激增，2023 年单年就有 287 题涉及，2024 年达到峰值 413 题，2025 年仍保持 401 题的高位，可见该知识点在初赛中的比重持续上升。

未来预测

基于上述趋势，可以合理预测：在未来几年的 NOIP 提高组初赛和 GESP 一级至四级考试中，字符串子串计数仍将是必考内容，且可能会以更灵活的形式出现，比如结合其他基础概念（如子串哈希、子串匹配长度等）出一道稍复杂的计算题。暂无足够依据预测具体题型变化，但掌握这一基础计数方法，对应对后续更复杂的字符串问题至关重要。