试题-设S为一个长度为n的字符串,其中的字符各不相同,则S中的互异的非平凡子串(非空且不同于S本身)的个数为()

题目

设S为一个长度为n的字符串,其中的字符各不相同,则S中的互异的非平凡子串(非空且不同于S本身)的个数为()

A.2n-1

B.n²

C.(n²/2)+(n/2)

D.(n²/2)+(n/2)-1

E.(n²/2)-(n/2)-1

上一题 下一题

解答

正确答案是 D

算第一个字母开头的，有n个（其中包括s本身）

第二次字母开头的， n-1个

一直到1个

n + (n-1) + .... + 1 = n(n+1) / 2

然后减去一个 s本身

C 6条回复评论

梦里不知身是客

是道好题，会了这道就能举一反三

发表于 2022-05-07 23:00:00

0 0

小可爱

长度为1的互异的非平凡子串有n个

长度为2的互异的非平凡子串有n-1个

长度为3的互异的非平凡子串有n-2个

。。。

长度为n-1的互异的非平凡子串有2个

长度为n的子串是本身，不是互异的非平凡子串。

所以，共有n+(n-1)+(n-2)+...+2 = (n+2)*(n-1)/2 = n*n/2+n/2-1

发表于 2018-10-13 15:33:49

0 0

资深90后

呵呵，整数乘法并不符合分配律，因此d是错的，正确答案应该是（n2+n）/2-1，所以选f

发表于 2018-10-13 15:33:38

0 0

粽子

【答案】B

【解析】题目说了一大堆，其实就是为了求字符串的非空真子串吗！字符串的子串，就是字符串中的某一个连续片段。截取一个字符串长度需要一个起始位置和结束位置。举个例子：“software”有8个字符，可是设置间隔的位置有9个，使用C(9,2)=36即可求得“software”的所有非空子串。因为一般情况下，我们也认为空串也是子串，故还需要加上1，总共37个子串。

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

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

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

编辑于 2016-10-06 10:28:41回复(4)