北京海淀区信息学竞赛 · 2023 北京市海淀区信息学竞赛（初赛）试题 第 6 题

如果字符串 $s$ 在字符串 $T$ 中出现了，则字符串 $s$ 被称作字符串 $T$ 的子串。设字符串 $T = \texttt{Olympic}$，$T$ 的非空子串的数目是（ ）。

这题只要盯着'非空子串'和'连续'这两个词，直接套用公式 n(n+1)/2 就能秒杀，千万别自己手动枚举去数，容易数漏数重。

最容易栽跟头的就是被'重复子串'带偏，比如看到'olympic'里有个'oly'，又有个'olympic'，就以为要去重。其实题目问的是'子串的数目'，不是'不同子串的种类数'。只要位置不同，哪怕内容一样也算两个。还有学生容易把子串和子序列搞混，子序列可以不连续，这题必须连续。

这道题考的是字符串处理里最基础的子串计数，核心就是公式 n(n+1)/2。命题人挖坑就坑在'重复字符'和'子串定义'上，爱让学生以为有重复就要去重，或者把子串当成子序列来算。拿到题先想：子串是连续的一段，长度为 n 的字符串里，长度为 1 的有 n 个，长度为 2 的有 n-1 个……一直到长度为 n 的只有 1 个，加起来就是 n+(n-1)+…+1，也就是 n(n+1)/2。这题 T='Olympic'，长度 n=7，直接套公式 7×8/2=28，选 A。避坑指南：含重复字符的字符串，'不同子串'数确实会少于理论最大值，但题目没问'不同子串'，问的是'数目'，所以重复的不影响计数，别自己脑补去重。考频趋势：字符串子串计数是 CSP-J/S 高频考点，近五年在初赛和复赛都出现过，平均每年考 1-2 次，属于必考基础。预测：未来大概率还会以这种纯计算或简单枚举的形式出现，难度不会突然跳到动态规划，但可能会换个问法，比如'长度为 k 的子串个数'或'包含某个特定字符的子串个数'，考生只要守住公式和定义，基本不会翻车。