小编Mod*_*Mod的帖子

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

例如,在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]不明显.

我想知道一个算法来找出数组中三个元素的最大xor值.我已经阅读了关于数组中两个元素的最大xor但是无法理解如何应用它来查找数组的3个元素的XOR的最大值.有人能指出一个暗示吗？

所需的复杂度:小于O(N ^ 3)其中N是数组中元素的数量.

例:

A = [1,2,3,4]

所有可能的三胞胎: -

1 ^ 2 ^ 3 = 0
1 ^ 2 ^ 4 = 7
1 ^ 3 ^ 4 = 6
2 ^ 3 ^ 4 = 5

因此,最大XOR值为7.

编辑:

我想到了一个复杂度为O(N ^ 2*log(MAX))的解决方案,它解决了我的目的:D.

MAX =阵列中的最大值

我们有一个字符串S,我们想要计算通过旋转字符串可以形成的不同字符串的数量.

例如 :-

S ="aaaa",这里是1字符串{ "aaaa" }

S ="abab",这里将是2个字符串{ "abab","baba" }

那么,有没有一种算法可以在O(| S |)复杂度中解决这个问题,其中| S | 是字符串的长度.