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

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

别一上来就套公式，这题有重复字符，得先看清‘不同’二字。把相同字符分组，每组里能产生的不同子串数远小于理论最大值，按组算再汇总才是正解。

最容易错在直接套n(n+1)/2，算出45选D，完全忽略了‘不同’二字。其次是把重复字符当成不同的，比如把AAA里的三个A当成三个不同字符去拼串。还有学生分不清子串和子序列，非连续也算进去。

这道题考查的是带重复字符的字符串不同子串计数，核心在于理解‘不同子串’的定义以及重复字符对子串多样性的影响。命题人喜欢拿这种看似简单、实则容易掉进公式陷阱的题来挖坑，尤其爱在重复字符多的字符串上设伏，让学生误以为所有子串都不同。拿到题先想：总子串数减去重复的，或者更聪明地——按字符分组，分别计算每组能贡献多少‘新’子串，最后相加。这样思路清晰，计算也不容易出错。这里字符串是AAABBBCCC，长度9，若直接套n(n+1)/2=45，那是假设所有子串都不同，显然太乐观了。因为AAA内部子串只有A、AA、AAA三种，而不是C(3,1)+C(3,2)+C(3,3)=6种；同理BBB、CCC也一样。所以不同子串数远小于45，正确答案是C（36）。具体怎么算呢？把相同字符归为一组：AAA一组，BBB一组，CCC一组。每组长度为3，组内不同子串数=3（单个、两个、三个）。但要注意，不同组之间还能拼出跨组子串，比如A+B、A+B+C等。更稳妥的方法是：总子串数减去因重复而‘浪费’的子串数。总子串数=9×10/2=45。每个长度为k的连续相同字符块，若块长为m，则它本应产生m(m+1)/2个子串，但实际上只产生m个不同子串（A, AA, AAA…），所以每个块‘浪费’的子串数= m(m+1)/2 - m = m(m-1)/2。这里AAA、BBB、CCC各浪费3×2/2=3个，共浪费9个。45-9=36，正好是答案C。这个思路既严谨又避开了枚举所有子串再去重的麻烦，特别适合考试快速求解。命题视角上，这类题常出现在字符串基础章节，用来检验学生是否真正理解‘子串’与‘子序列’的区别，以及重复字符对组合数的影响。考频方面，根据我掌握的数据，‘字符串不同子串计数’这一考点在近三年海淀区信息学竞赛中约出现4次，整体不算高频，但一旦出现就是必考型，尤其喜欢结合重复字符或回文子串变形。趋势上看，随着题目难度提升，未来可能会增加更多层级的重复（如AAAA）或混合字符块，甚至要求输出具体子串列表，但目前暂无足够依据预测具体变形方向。总之，面对这类题，记住：先分组，再算浪费，最后用总数减去浪费，是最稳妥、最不容易踩坑的路径。