如何计算substring数量

一道长度<10^6的string，找出其不重复的substring数目

建出后缀树以后遍历一下就可以了，不知道有没有更简单的做法。。。

暴力解是Time O(n^2), Space O(n)

字符串长度是10^6。看数据规模，应该是O(n)的算法(或者是更快的某种Math算法）。

O(n*log(n))应该也太慢，所以binarysearch的思路应该不行。

Disclaim: 暂时，还没想到。

非常经典的后缀数据结构解决的问题。lz可以看一下后缀自动机或者后缀数组的实现....

rsents 发表于 2019-9-23 04:02
非常经典的后缀数据结构解决的问题。lz可以看一下后缀自动机或者后缀数组的实现....

嗯嗯问了一个省队的同学他秒答……谢谢了

最近做过一道subsequence的题。我的思路是：

如果是每个字符，如果是distinct，那么他能够构成的是当前所有的distinct的subsequence的数量+1。

但是如果是重复字母，因为以他结尾的subsequence以前已经见过，所以要剪掉所有的以前的以他结尾的subsequence的数量。

举例子：

1.           a         b       a       b       a
   
2. -----------------------------------------------
   
3.        0+1=1    1+1=2  3+1=4   6+1=7   11+1=12
   
4.   ↗️    ⬇️             4-1=3   7-2=5   12-3-1=8
   
5. 0 ->  0+1=1    1+2=3  3+3=6   6+5=11  11+8=19

复制代码