字符串的非空子串个数

对于一个长度为n的字符串，它的非空子串个数为 $C_n^1+C_n^2+...+C_n^{n-1}$，即从中选择1个字符的子串数目 + 从中选择2个字符的子串数目 + ... + 从中选择n-1个字符的子串数目。

可以用以下代码实现：

def count_substrings(s):
    n = len(s)
    res = 0
    for i in range(1, n+1):
        res += n - i + 1
    return res

s = 'abcde'
print(count_substrings(s))  # 输出 15

相关问题

一个字符串的非空子串是指字符串中长度至少为1的连续的一段字符组成的串。例如，字符串aaab有非空子串a,b,aa,ab,aaa,aab,aaab一共七个。注意在计算时，只算本质不同的串的个数。 请问，字符串0100110001010001有多少个不同的非空子串？

将字符串分解为所有长度的子串，计算每个子串的本质不同的个数，然后将它们相加即可。

例如，对于长度为3的子串，可以分别计算它们的本质不同个数：

010 -> 2
100 -> 2
001 -> 2
110 -> 2
000 -> 1
101 -> 2
010 -> 2
100 -> 2
001 -> 2
010 -> 2
101 -> 2
010 -> 2
001 -> 2
010 -> 2
101 -> 2
010 -> 2

共计18个不同的本质不同的子串。

对于长度为1和2的子串也做同样的计算，最终得到总共的本质不同的非空子串个数为：

1 + 18 + 14 + 6 + 1 = 40

所以字符串0100110001010001有40个不同的非空子串。

一个字符串的非空子串是指字符串中长度至少为 1 的连续的一段字符组成 的串。例如，字符串aaab 有非空子串a, b, aa, ab, aaa, aab, aaab，一共 7 个。 注意在计算时，只算本质不同的串的个数。 请问，字符串0100110001010001 有多少个不同的非空子串？

这段二进制字符串说的是一个非空字符串是指字符串中长度至少为 1 的连续的一段字符组成的串。例如，字符串 aaab 有非空字符串 a, b, aa, ab, aaa, aab, aaab，一共 7 个。注意在计算时，只算本质不同的串的个数。请问，字符串 10100110001010001 有多少个不同的非空子串？