NOIP 普及组初赛 · NOIP 2012 普及组初赛试题第 19 题

选择题 · 答案 C · 考点：字符串(string)

题目

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

答案：C

字符串(string)

这题不能直接套公式，得先数出AA、BB、CC各自能贡献几个不同子串，再把AB、BC、ABC这些混合子串加起来。

最容易把答案算成45，就是忘了AAABBBCCC里A、B、C都重复了，直接用n(n+1)/2会算出所有子串数，但题目要的是不同子串。还有人会漏掉跨字符的组合，比如只数了AA、AB、BA，忘了ABC、ABB、BCC这些。

这题考的是去重计数：字符串的子串定义是连续片段，但题目要求“不同的”子串。命题人喜欢用重复字符来挖坑，让学生以为直接套公式就行，其实得把重复产生的相同子串剔除。

子串就是原串里切出来的一段连续字符。比如AAABBBCCC里，"AAB"是子串，"ABC"也是，但"ABA"不是，因为原串里A后面紧跟着B再后面是B，没有A。

第 9 题· NOIP 2008 普及组初赛试题 · 答案 A看解析 →
第 26 题· NOIP 2008 普及组初赛试题 · 答案 DBGEFCA看解析 →
第 27 题· NOIP 2008 普及组初赛试题 · 答案 change[i] >= 'A' && change[i] <= 'Z'change[i] <= 'Z'str[i] >= 'A' && str[i] <= 'Z'str[i] <= 'Z'str[i] = change[str[i] - 'a'];ChangeString();看解析 →
第 26 题· NOIP 2008 提高组初赛试题 · 答案 defghijxyzabc/hfizxjaybcccc看解析 →
第 22 题· NOIP 2011 普及组初赛试题 · 答案 3看解析 →

在 OI伴学里做这道题

登录后可计时作答、查看完整六段式解析，并按你的错题自动生成同类练习。