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

题目

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

A.1024

B.1018

C.55

D.50

上一题 下一题

解答

正确答案是 D

总的子串个数为 10+9+8+7+。。+1 = 55

其中w(两次）, ww, q, ., 有重复

55 - 5 = 50

C 5条回复评论

wyj

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

发表于 2021-09-13 22:40:00

0 0

岁月长歌

正确答案D。

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

以第一个w开头的子串：w，ww，www

以第二个w开头的子串：w，ww

以第三个w开头的子串：w

以第一个q开头的子串：q，qq

以第二个q开头的子串：q

以第一个.开头的子串：.

重复子串数：5

答案：55-5=50

发表于 2018-10-13 14:30:16

0 0

岁月长歌

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

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

如果求的是子序列，那么答案是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。

发表于 2018-10-13 14:30:05

0 0

几米的思维

要求的是子串，从左到右一次截取， 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

发表于 2018-10-13 14:29:50

0 0

改造家

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

发表于 2018-10-13 14:29:37

0 0

问题信息

分类：数据结构 - 字符串匹配

难度:

最新校招难题刷题，快来进刷题群吧