NOIP 普及组初赛 · NOIP 2008 普及组初赛试题 第 9 题

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

这题就是考子串计数公式。拿到字符串先数长度n，直接套n(n+1)/2算非空子串总数，别被选项里的29带偏，那是含空串的结果。

最容易掉进命题人挖的坑就是选B。公式n(n+1)/2算出来是28，但很多同学记混了，以为要加1算空串，或者看到选项有29就下意识选它。其实题目明确问“非空子串”，空串不算，所以28才是正解。另外要注意字符串长度别数错，Olympic一共7个字母，不是6个也不是8个，数错了整道题就废了。

考点与概念

这题考查的是字符串子串计数的基础公式。子串就是原串中连续的一段字符。对于长度为 n 的字符串，任意选取两个位置（包括首尾）就能确定一个子串，一共有 n(n+1)/2 种选法。

命题人怎么挖坑

命题人喜欢用“陷阱选项”来测试学生是否真的看清了题目要求。这里正确答案是 28，但选项 B 给了 29。29 其实是包含空串时的总数（公式 +1）。很多学生背公式不牢，或者看到 29 就以为是对的，结果掉进坑里。记住：非空子串就是 n(n+1)/2，含空串才是 n(n+1)/2 + 1。