BCSP-X · 2024 BCSP-X 下半年活动基础知识测评（小学高年级组） 第 11 题

原字符串中任意一段连续的字符所组成的新字符串称为子串，则字符串 $\tt{101010101}$ 共有（ ）个不同的非空子串。

拿到这种全是重复模式的字符串，千万别直接套公式 n(n+1)/2，那会算出最大子串数。这题的核心是“去重”，得先找规律，把重复的子串合并，再数剩下的不同个数。

最容易掉进的坑就是机械地用长度公式。比如这题长度9，公式能算出45个子串，但答案只有17，差得远。学生往往分不清“子串”和“子序列”，或者在去重时逻辑混乱，比如把“101”和“10101”这种包含关系搞错，或者漏掉那些虽然长但内容相同的子串。

这道题考查的是字符串处理中的子串概念以及去重计数。子串的定义很明确：原字符串中任意一段连续的字符组成的新字符串。很多同学看到“子串”就想到公式 n(n+1)/2，这是因为对于全不同的字符（如“abcde”），子串总数确实是这个数。但本题给出的字符串是“101010101”，里面全是 1 和 0，重复率极高，所以直接套公式会严重高估数量，这是命题人最喜欢挖的坑——用特殊结构干扰常规思维。

拿到题先想什么？不能盲目枚举，得找规律。观察这个字符串，它是“10”不断重复拼接而成的，总长度 9。我们可以按子串的长度来分类统计，这样条理清晰，不容易漏。

长度为 1 的子串：只有“1”和“0”两种，共 2 个。 长度为 2 的子串：只能是“10”或“01”，共 2 个。 长度为 3 的子串：可以是“101”或“010”，共 2 个。 长度为 4 的子串：可以是“1010”或“0101”，共 2 个。 长度为 5 的子串：可以是“10101”或“01010”，共 2 个。 长度为 6 的子串：可以是“101010”或“010101”，共 2 个。 长度为 7 的子串：可以是“1010101”或“0101010”，共 2 个。 长度为 8 的子串：可以是“10101010”或“01010101”，共 2 个。 长度为 9 的子串：只能是整个字符串“101010101”，共 1 个。

把所有不同子串加起来：2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 1 = 17。所以正确答案是 C。

这里有个细节要注意：为什么长度 1 到 8 都是 2 个？因为字符串以“1”开头，以“1”结尾，中间全是“10”循环。长度 1 时，首字符是 1，尾字符是 1，但中间有 0，所以能凑出“1”和“0”。长度 2 时，首尾都是 1，中间有 0，能凑出“10”和“01”。直到长度 8，首尾都是 1，中间有 0，依然能凑出两种。只有长度 9 时，首尾都是 1，中间有 0，但长度正好等于原串，只能取整串，所以只有 1 个。这个规律是解题的关键。

避坑方面，千万不要用双指针法暴力枚举所有子串再去重，那样代码量太大，容易出错，也不符合单选题快速解题的要求。这道题考的是观察力和分类讨论的能力，而不是编程实现。

从考频和趋势来看，BCSP-X 近年来越来越喜欢考这种“看似简单实则陷阱多”的概念题。字符串处理是 CSP-J/S 的常客，但像这样专门考察“重复子串去重”的题目，在历年真题中出现频率不算高，属于中等偏难的考点。未来可能会更多出现在字符串哈希、后缀数组等进阶知识点的前置铺垫中，或者结合回文串、周期串等概念一起考，难度会进一步提升。