试题-若串S=′software′,其子串的数目是()

题目

若串S=′software′,其子串的数目是()

A.8

B.37

C.36

D.9

上一题 下一题

解答

正确答案是 B

字串： n（n+1）/2 + 1

非空子串：n（n+1）/2

非空真子串：n（n+1）/2 - 1

C 9条回复评论

小茉莉

(单选题) 若串S=’software’，其子串数目为(包括空串)：这个是这道题的前一道题，我只想说，有意思吗？

发表于 2018-10-13 11:16:57

0 0

雨声敲敲

没有注意是单双引号

发表于 2018-10-13 11:16:48

0 0

企鹅哥哥

一个N长字符串的子串子算方法为：(N*(N+1)/2)+1，最后加1是因为所有字符串的子串都默认有空串，所以加1

发表于 2018-10-13 11:16:40

0 0

企鹅哥哥

若非特别提示，子串还包括该串本身，以及空串。而其本身和空串叫做“非平凡子串”，注意题中的提示，是否要除去。

发表于 2018-10-13 11:16:26

0 0

碎梦不是梦碎

从1+2+~~~+8=8（8+1）/2再加空串

发表于 2018-10-13 11:16:16

0 0

小可爱

串中任意个连续的字符组成的子序列称为该串的子串

ab的子串：a、b、ab和一个空子串共4个即（2+1+1）个，abc的子串：a、 b、 c、 ab、 bc 、abc和一个空子串共（3+2+1+1）个，所以若字符串的长度为n,则子串的个数就是[n+(n-1)+.......+1+1]个，"software"中非空子串的个数就是8+7+....+1=36个。

发表于 2018-10-13 11:16:10

0 0

小可爱

非空字串的个数为：n（n+1）/2

所以最后应该再加1，即37

发表于 2018-10-13 11:15:44

0 0

落地98K

晕，忘了空串也是串！

发表于 2018-10-13 11:15:37

0 0

浅色回忆

链接：https://www.nowcoder.com/questionTerminal/939250fe276340d798e136c997f8fe0c
来源：牛客网

答案】B

【解析】 字符串的子串，就是字符串中的某一个连续片段。截取一个字符串长度需要一个起始位置和结束位置。字符串“software”有8个字符，可是设置间隔的位置有9个，使用C(9,2)=36即可求得字符串“software”的所有子串。因为题目标明空串也是子串，故还需要加上1，总共37个子串。所以答案选B。

含有n个不同字符的字符串的非空子串的个数为C(n + 1, 2) = n * (n + 1) / 2

子串（包括空串）为 n * (n + 1) / 2 + 1

非空真子子串（不包括空串和跟自己一样的子串）为 n *（n + 1）/ 2 - 1

发表于 2020-11-01 10:04:55

0 1

问题信息

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

难度:

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