首页字符串的非空子串个数

字符串的非空子串个数

时间: 2023-08-21 18:06:28 浏览: 282

快速求一个字符串的非空子串(不相同)的数量

5星 · 资源好评率100%

题目（求字符串的非空子串数量）一个字符串的非空子串是指字符串中长度至少为 1 的连续的一段字符组成的串。例如，字符串aaab 有非空子串a, b, aa, ab, aaa, aab, aaab，一共 7 个。注意在计算时，只算本质不同的串的个数。请问，字符串0100110001010001 有多少个不同的非空子串？题目分析 //通过题目可知要求的是不同的非空子串，set方法可以去重，set方法有两个子方法，一个是HashSet，另一个是TreeSet。 //subString(i,j)是求字符串的子串从下标 i 开始，到 j 结束。类似于指针移动。简谈HashSet和TreeSet

对于一个长度为n的字符串，它的非空子串个数为 $C_n^1+C_n^2+...+C_n^{n-1}$，即从中选择1个字符的子串数目 + 从中选择2个字符的子串数目 + ... + 从中选择n-1个字符的子串数目。可以用以下代码实现： ```python 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 ```

阅读全文