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

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

别一上来就套 n(n+1)/2 公式，这题有重复字符，直接算会多。先想清楚：不同子串 = 所有子串总数 - 重复出现的子串。这道题里，A、B、C 各自能组成的纯同字符子串（如 AA、AAA）是重复的，其他混合子串（如 AB、ABC）没有重复，所以只要把 A、B、C 各自的重复部分减掉就行。

最容易栽跟头的就是死记公式 n(n+1)/2，算出 36 就选 C，完全没看题里字符重复。还有人分不清子串和子序列，把不连续的也算进去。另外，去重时只减了 AA、BB、CC，忘了 AAA、BBB、CCC 这些更长的同字符子串也重复了，结果还是多算。

这道题考查的是字符串子串的概念以及如何处理重复字符带来的去重问题。命题人喜欢在这种纯计算题里埋坑：明明给了 n(n+1)/2 这个漂亮公式，结果因为字符重复，不同子串的数量远小于理论最大值。如果只背公式，看到 3 个 A、3 个 B、3 个 C 就机械代入，一定会选错。

先理清概念：子串必须是连续的一段。原串 AAABBBCCC 长度 n=9，理论上的子串总数是 9×10÷2=45 个。但这 45 个里，有很多是重复的，比如 AA 出现了两次，AAA 出现了两次，BB、BBB、CC、CCC 同理。题目问的是“不同的”非空子串，所以必须把重复的去掉。

怎么算去重？观察发现，只有纯同字符的子串会重复，像 AB、ABC、ABBB 这种混合子串在原串里只出现一次，不用管。那重复的有哪些？

• 字符 A：长度 1 的 A 有 3 个（重复 2 次），长度 2 的 AA 有 2 个（重复 1 次），长度 3 的 AAA 有 1 个（重复 0 次）。所以 A 贡献的重复子串数是 2+1=3。
• 字符 B：同理，长度 1 的 B 重复 2 次，长度 2 的 BB 重复 1 次，共 3 个重复。
• 字符 C：同理，也是 3 个重复。

总重复数 = 3+3+3 = 9。因此不同子串数 = 45 - 9 = 36。

这里有个易错点：有人会只减 AA、BB、CC 这 3 种，忘了 AAA、BBB、CCC 这些更长的同字符子串其实也重复了（虽然它们各自只出现一次，但它们对应的“重复量”在计算时要考虑长度大于等于 2 的情况）。还有人会把子序列混进来，那就会算出更大的数。双指针枚举所有子串再哈希去重是通用做法，但这对选择题太繁琐，直接找规律扣重复数最快。

考频与趋势：在 CSP-J/S 和 GESP 的历年真题中，字符串子串计数这类题出现频率中等，常作为单选压轴或填空压轴。2023 年 CSP-J 第 10 题考了子串回文数，2022 年 GESP 第 12 题考了子串不同字符数，可见命题人偏爱用“重复字符”制造陷阱。未来大概率还会考类似题型，要么换字母组合，要么考子串哈希、子串回文等变体，核心都是“先算总数再扣重复”。

所以，这道题正确答案就是 C：36。记住，看到重复字符，别急着套公式，先想怎么扣重复。