数据结构问题,设S是一个长度为n的字符串,其中字符各不相同,则S中的互异非平凡子串（非空切不同于本身）个数为————.A.2的(n-1)次方B.n(n+1)/2C.n(n+1)/2-1D.n(n-1)/2-1答案解析是这样的：长度

Question

数据结构问题,设S是一个长度为n的字符串,其中字符各不相同,则S中的互异非平凡子串（非空切不同于本身）
个数为————.
A.2的(n-1)次方 B.n(n+1)/2 C.n(n+1)/2-1 D.n(n-1)/2-1
答案解析是这样的：长度为n-1的不同子串个数为2,长度为n-2的不同子串个数为3..,长度为1的不同子串个数是n,综合得到C

Answer 1

比如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
这个公式是初中数学里面的吧.