必考题

考点

数据结构-字符串-字符串匹配

面5笔5

字符串www.qq.com所有非空子串（两个子串如果内容相同则只算一个）个数是（）

A.1024

B.1018

C.55

D.50

胡俟

2025-09-01 22:00:00

双非一本，荒废了三年，目前在准备考研冲211，但是现在计算机考研太难了，要是没考上的话估计也是找不到工作了，什么语言都学过一点，但是没有项目经历，只做过学校的一些小任务。我现在好焦虑，是努力考研还是从现在开始为找工作做准备，暑假开始还能在秋招中拿offer吗？

0 0

wyj

2021-09-13 22:40:00

哎呀，我居然把他看完了，谢谢大佬的文章

0 0

岁月长歌

2018-10-13 14:30:16

正确答案D。

子串总数：10+9+8+.....+1=55

0 0

岁月长歌

2018-10-13 14:30:05

注意两个概念：子串与子序列。

子串是从原字符串中连续截取得到的；而子序列则不要求连续，即可以是离散截取的。

如果求的是子序列，那么答案是B. 1018。具体计算是： 2^10 = 1024 个子序列，减去空串1个为1023，再减去子序列长度为1时重复的2个w和1个q为1020，最后再减去子序列长度为2时重复的2个ww，只剩下1018个不重复的子序列。

现在求的是子串，则只有 1 + 2 + 3 + ... + 10 = 55 个，减去重复的两次w，一次q，一次.，一次ww，只剩下 50 个不重复的。

选D。

0 0

几米的思维

2018-10-13 14:29:50

要求的是子串，从左到右一次截取， 10个字符的子串，1个; 9个字符的子串，2个; 8----------------------3 7----------------------4 ......... 1----------------------10 共有:1+2+3+...+10=10*(10+1)/2=55 减去重复的: 1个字符时有3个w,2个q,2个. 2个字符时有2个ww 故应减去:(2+1+1+1)=5 答案:55-5=50

0 0

改造家

2018-10-13 14:29:37

非空子串的个数共有n(n+1)/2=55个，由于相同子串算一个，所以要减去2个w，一个.，一个ww，一个q，所以还有50个

0 0