arrays - 不同子阵列的数量

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

为这个数组构造后缀树。然后将这棵树中所有边的长度加在一起。

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