课堂练习

1. 【NOIP2008】设字符串 $S = "Olympic"$ ，S的非空子串的数目是( )。
   A. 28
   B. 29
   C. 16
   D. 17
   【答案】A
   【分析】长度为1的有7个，长度不为1的有 $C_{7}^{2}=21$ 个（首尾各取一个位置），总数为28。也可以用另外一种枚举的方法： $7 + 6 + 5 + 4 + 3 + 2 + 1 = 28$ （取1个字符，取2个字符，…）。
2. 【NOIP2012】原字符串中任意一段连续的字符组成的新字符串称为子串。则字符串 "AAABBBCCC"共有( )个不同的非空子串。
   A. 3
   B. 12
   C. 36
   D. 45
   【答案】C
   【分析】枚举：这题和上面那题的区别在于子串会出现重复的情况。总共长度9，可以手动寻找全部的不同非空子串。长度为1的有3个：A、B、C；长度为2的有5个：AA、AB、BB、BC、CC；长度为3的有7个：AAA、AAB、ABB、BBB、BBC、BCC、CCC；长度为4的有6个：AAAB、AABB、ABBB、BBBC、BBCC、BCCC；长度为5的有5个：AAABB、AABBB、ABBBC、BBBCC、BBCCC；长度为6的有4个：AAABBB、AABBBC、ABBBCC、BBBCCC；长度为7的有3个：AAABBC、AABBBCC、ABBBCCC；长度为8的有2个：AAABBBCC、AABBBCCC；长度为9的有1个：AAABBBCCC，共计36个。
3. 【NOIP2017】若串S = "copyright"，其子串的个数是( )。
   A. 72
   B. 45
   C. 46
   D. 36
   【答案】C
   【分析】空串算1个，非空串的情况可以考虑在字符串中任取两个位置作为左端和右端得到的子串，方法数是 $C_{10}^{2}=45$ ，合起来就是46。
4. 【NOIP2016】以下关于字符串的判定语句中，正确的是( )。
   A. 字符串是一种特殊的线性表
   B. 串的长度必须大于零
   C. 字符串不可以用数组来表示
   D. 空格字符组成的串就是空串
   【答案】A
   【分析】本题采用排除法。字符串允许为长度为0的空串，排除B选项；字符数组也可以实现字符串功能，排除C选项；空串指的是不包含任何字符，长度为0的字符串，因此排除D选项。