首页 > 试题广场 > 设S为一个长度为n的字符串,其中的字符各不相同,则S中的互异
[单选题]
设S为一个长度为n的字符串,其中的字符各不相同,则S中的互异的非平凡子串(非空且不同于S本身)的个数为()
  • 2n-1
  • (n²/2)+(n/2)
  • (n²/2)+(n/2)-1
  • (n²/2)-(n/2)-1
  • 其他情况
选择题嘛,把n=1代入就可以了。
发表于 2015-08-21 23:21:52 回复(19)
D

算第一个字母开头的, 有n个 (其中包括s本身)
第二次字母开头的, n-1个
一直到1个

n + (n-1) + ....  + 1 = n(n+1) / 2 
然后 减去一个 s本身
编辑于 2017-05-03 10:41:33 回复(7)
【答案】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)
n个字符取连续子串,只考虑子串的开头和结尾两个点的选择,相当于从n+1个分割点中选两个进行分割,一共是(n+1)n/2,再减掉字符串本身,答案是n*n/2+n/2-1。
发表于 2015-08-02 09:07:06 回复(5)
长度为N的串,其子串个数: (N + N-1 + N-2 + ... + 2 + 1 ) = N ( N + 1 ) / 2;
即子串长度为1的个数:N;
子串长度为2的个数:N-1;
...
子串长度为N的个数:1;
累加即可。
看清题目要求,如果包含空串,则总个数:N(N+1)/2 + 1
如果不包含空串,也不包含本身,则总个数:N(N+1)/2 - 1

发表于 2016-08-27 17:34:44 回复(0)
那s="abcdefg"为例:
字符串长度为1的字符串子集分别为:"a","b", "c", "d", "e", "f",”g“;共6个(个数为n)
字符串长度为2的字符串子集分别为:"ab","bc", "cd", "de", "ef", "fg";共5个(个数为n-1)
字符串长度为3的字符串子集分别为:"abc","bcd", "cde", "def", "efg" ;共4个(个数为n-2)
字符串长度为4的字符串子集分别为:"abcd","bcde", "cdef", "defg" ;共3个(个数为n-3)
字符串长度为5的字符串子集分别为:"abcde","bcdef", "cdefg" ;共2个(个数为n-3)
所示是首项为2的等差数列,求和sum=(n-1)(2+n)/2=n^2/2 +n/2 -1
发表于 2015-09-28 16:14:15 回复(2)
估计有很多和我一样的渣渣看到这种题就懵b了,我发个解析,网上的解法

比如S字串为"abcdefg",长度为7.则S中的包含的互不相同的字串有如下一些:
1.长度为6的个数为2:"abcdef"和"bcdefg"
2.长度为5的个数为3:"abcde","bcdef","cdefg"
.
6.长度为1的个数为7:"a","b","c","d","e","f","g"
个数总和就是2+3+4+5+6+7 = (1+2+3+..+7) - 1 = 7x(7+1)/2 - 1.
其中:
1+2+3+...+n = (1+n) + (2+(n-1)) + (3+(n-2)) + ...(首尾两项相加的和都是n+1,共 n/2个)
= n(n+1)/2 
这个公式是初中数学里面的吧.
发表于 2019-08-29 11:11:37 回复(0)
含有n个不同字符的字符串的非空子串的个数为C(n + 1, 2) = n * (n + 1) / 2 
子串(包括空串)为 n * (n + 1) / 2 + 1 
非空真子子串(不包括空串和跟自己一样的子串)为 n *(n + 1)/ 2 - 1
发表于 2019-02-26 10:14:13 回复(0)
n个不同"字符串",求其"子串" ((n*(1+n))/2)+1 除去空串-1,除去自身-1, 故((n*(1+n))/2)+1-1-1 =>((n*(1+n))/2)-1
编辑于 2018-09-22 23:09:19 回复(1)
呵呵,整数乘法并不符合分配律,因此d是错的,正确答案应该是(n2+n)/2-1,所以选f
发表于 2017-09-15 16:56:36 回复(0)
首先,是子串不是子序列,所以需要连续的字符组成的才算;
其次:
n 1
n-1 2
...
1 n
累计((n+1)*n)/2个,
最后,去掉长度为n的s本身
合计 答案就有了
发表于 2017-01-10 16:37:24 回复(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

发表于 2015-08-28 23:53:48 回复(0)

推算好后

最好代入一下简单例子,检验正确性

发表于 2019-09-07 23:03:16 回复(0)

子串:串中任意个连续的字符组成的子序列称为该串的子串(连续、连续、连续!重要的事情说三遍)

题目要求:非平凡子串(非空且不同于S本身)

特值法带入2-3个试试,就差不多没跑了

编辑于 2019-05-21 11:52:48 回复(0)
n个字符取连续子串,只考虑子串的开头和结尾两个点的选择,相当于从n+1个分割点中选两个进行分割,即数学中的组合C-n-2,即(n+1)n/2,再减掉字符串本身,答案是n*n/2+n/2-1。
发表于 2019-04-03 11:32:43 回复(0)
类似于这样的题目,带入常数,取n为某个值即可
发表于 2018-06-27 09:41:33 回复(0)
特殊值代入法
发表于 2018-05-12 23:53:41 回复(0)
长度为1的真子串的个数为n,长度为2的真子串的个数为n-1,长度为3的真子串的个数为n-2,...,以此类推,长度为n-1的真子串的个数为2,所以总的子串个数为2+...+n   =   n*(n+1)/2-1
发表于 2018-04-11 20:36:36 回复(0)
代入=1快速对比答案
发表于 2018-03-22 19:58:26 回复(0)
非空且不同于S本身,注意这个条件
发表于 2017-09-05 15:23:12 回复(0)