如何找到xor 0的所有子数组？

Question

问题是找到给定数组的所有子数组，其所有元素的xor都等于零。

例如，如果数组包含元素[13,8,5,3,3]，则解决方案应该给出所有子数组的索引，如0-2、3-4、0-4等。

这个问题类似于向here提出的问题。

唯一的区别是我想要所有满足方程A0 xor A1 xor...xor An = 0的子数组的索引。

Answer 1

这是对相关问题的一个相当直截了当的扩展。在Python里，

# Multivalued map from the XOR of array[:i] to i for all i.
prefix_xor_to_stops = {0: [0]}
prefix_xor = 0
for j, x in range(array):
    prefix_xor ^= x
    # Returns the value associated with prefix_xor. Inserts [] if not present.
    stops = prefix_xor_to_stops.setdefault(prefix_xor, [])
    for i in stops:
        yield (i, j+1)
    stops.append(j+1)

和前面一样，我们的想法是子数组array[i:j]有XOR零当且仅当array[:i]的XOR等于array[:j]的XOR。对于数组的每个后续元素，我们从前缀的XOR开始计算前缀以该元素结尾的XOR，然后查找上述方程的所有解决方案i。然后插入新的关联并继续。

Answer 2

如果你想修改文章中提到的答案，那么我希望你对这个解决方案有很好的理解。现在，该解决方案中缺少的是，它只存储特定前缀xor和的第一个索引出现。没有跟踪发生相同xorSum的其他索引。因此，您需要做的是修改映射，为每个C++保留索引列表(向量在xorSum中)。

Answer 3

如果数组有两个不同的前缀具有相等的xor，那么假设长度x1的前缀和长度x2的前缀，那么从x1 +1到x2的子数组的xor等于0。制作一个字典(BST，哈希表，任何类似的)并存储在那里的值(前缀和的值，前缀给出这个值)。任何两个具有相同值的元素都会给您一个子数组。如果你愿意的话，你也可以使用Trie找到它。

使用Trie：

在开始时，Trie由单个节点和无边组成。我们想把数字加进去。还可以方便地对它们进行索引，因为我们希望找到所有的子数组。在Trie中表示某些数字(在重复情况下是多个)的每个节点将存储它们的索引列表，因此我们可以很容易地获得子数组。

当我们用索引i添加一个数字n时，我们把n写成一个二进制数。我们从初始节点开始。如果n的最重要位等于0，如果从一开始就有一个标记为0的边，那么我们移动到相应的顶点，如果没有创建一个指向新节点的新边，那么我们就移到这个新创建的边(对于1来说是相同的)。然后我们继续这样做，直到遍历n的每一点。我们将索引i添加到节点中的索引列表中。

1. 使变量prefsum =0
2. 对于每一个i=1到n：
   • 用索引i向Trie添加prefsum
   • 集预量=预量^ arrayi
   • 检查Trie中是否存在值预和。对于每个这样的值v，xor =0的子数组在索引v-th和i-th之间。

​

总复杂度为O(n *log(数组中的最大值))

它可能并不比使用BST或哈希数组更好，但是它是一个流行的技巧，特别是在XOR操作的一些问题上。