求解字符串"aaabccbdef"全部非空子串（两个子串如果内容相同则只算一个）个数

求解字符串"aaabccbdef"所有非空子串（两个子串如果内容相同则只算一个）个数
RT
[解决办法]
python解法

print(len(set("aaabccbdef")))

答案 6
[解决办法]
用哈希
[解决办法]
方法如3楼,答案是29.
[解决办法]
是个例子还是就这么长？
如果字符串长度不是特别长的话，简单循环就是了，用map记录一下，查找是否重复
时间空间复杂度大概是o(n*n)
[解决办法]

引用:

方法如3楼,答案是29.

29?大概不止
单个是6
2个是7
3个是8
4个是7
5个是6
6个是5
7个是4
8个是3
9个是2
10个是1
一共49好像，目测，没检查
只有这么点数据的话没必要用哈希
[解决办法]
直接统计后缀树的节点个数（包括非叶节点）不就完了……
虽然构造后缀树是个不简单的工作。
[解决办法]

引用:

顺便后缀树可以线性，你要写nlogn也可以。

线性时间构造后缀树显然是个高级+难写的算法.您为什么不说直接用后缀数组统计呢?
[解决办法]
这个问题还有些意思，只求个数的话不用完全生成最后的O(n^2)个串，转走了。

查看更多 下一篇