不同子阵列的数量

Question

我想找到一个算法来计算数组的不同子数组的数量.

例如,在A = [1,2,1,2]的情况下,不同子阵列的数量为7:

{ [1] , [2] , [1,2] , [2,1] , [1,2,1] , [2,1,2], [1,2,1,2]}  

在B = [1,1,1]的情况下,不同子阵列的数量为3:

{ [1] , [1,1] , [1,1,1] }

甲子阵列是一个连续子序列,或切片,阵列.区别意味着不同的内容; 例如:

来自A [0:1]的[1]和来自A [2:3]的[1]并不明显.

同样地:

B [0:1],B [1:2],B [2:3]不明显.

Answer 1

构造此数组的后缀树.然后将此树中所有边的长度相加.

构造后缀树所需的时间是O(n)和适当的算法(Ukkonen或McCreight的算法).遍历树并将长度加在一起所需的时间也是O(n).