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

Question

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

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

问题与

中的问题相似

唯一的区别是我想要满足方程A0 xor A1 xor...xor An = 0

的所有子数组的索引

Answer 1

如果你有两个不同的数组前缀，它们的异或相等，假设长度为 x1 的前缀和长度为 x2 的前缀，那么从 x1 + 1 到 x2 的子数组的 xor 等于 0。制作字典 (BST, hash table，任何类似的）并在那里存储对（前缀和的值，给出该值的前缀）。任何两个具有相同值的元素都会给你一个子数组。如果你愿意，你也可以使用 Trie 查找它。

使用特里树：

一开始Trie由单节点组成，没有边。我们想给它加上数字。索引它们也很方便，因为我们想找到所有子数组。 Trie 中表示一些数字（如果重复则为多个）的每个节点将存储其索引列表，因此我们可以轻松获取子数组。

当我们将一个数字 n 与索引 i 相加时，我们将 n 写为二进制数。我们从初始节点开始。如果 n 的最高有效位等于 0，如果从一开始就存在标记为 0 的边，那么我们移动到相应的顶点，如果不存在，我们创建一个标记为 0 的新边指向一个新节点，然后我们移动到这个新创建的一个（1 同样的事情）。然后我们继续这样做，直到我们遍历 n 的每一位。我们将索引 i 添加到我们最终所在的节点中的索引列表中。

使变量 prefsum = 0
对于每个 i = 1 到 n：
- 将 prefsum 添加到索引为 i 的 Trie
- 设置prefsum = prefsum ^ array[i]
- 检查Trie中是否存在value prefsum。对于每个这样的值 v，xor 等于 0 的子数组在索引 v-th 和 i-th 之间。

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

它可能并不比使用 BST 或哈希数组更好，但它是一种流行的技巧，尤其在一些 XOR 运算的问题中表现出色。

Answer 2

这是对链接问题的一个相当直接的扩展。在 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] 的异或等于 array[:j] 的异或时，子数组 array[i:j] 的异或为零。对于数组的每个后续元素，我们计算以该元素结尾的前缀与以前一个元素结尾的前缀的异或，然后查找上述等式的所有解 i。然后我们插入新的关联并继续。

Answer 3

如果您想修改 post 中提到的答案，那么我希望您已经很好地理解了该解决方案。现在该解决方案中缺少的是它仅存储特定前缀 xor 和的第一个索引出现。不跟踪出现相同 xorSum 的其他索引。因此，您要做的是修改 map 以保留每个 xorSum 的索引列表（C++ 中的向量）。

Answer 4

我会在Python3.7

写代码块

令 l 为 (i,j) 的元组列表

最有效和最简单的处理问题的方法是：

第 1 步：计算前缀的异或：

xorArr[0] = arr[0] #here arr = [13,8,5,3,3]
for i in range(1, n): 
    xorArr[i] = xorArr[i - 1] ^ arr[i]

第2步：检查是否在任何一点xorArr[i]=0，如果是则arr[:i+1]是一个异或为零的子数组：

for i in range(1, n): 
    xorArr[i] = xorArr[i - 1] ^ arr[i] 
    if xorArr[i]==0:
        l.append((0,i))

第 3 步：现在创建一个字典来存储 xorArr 中出现的每个元素的索引列表

d = {xorArr[0]:[0]}
for x in range(1,n):
    if xorArr[x] in d.keys():
        d[xorArr[x]].append(x)
    else:
        d[xorArr[x]] = [x]

第 4 步：创建一个函数，为 d[xorArr[x]] 中的每个元素配对 (i,j) 并将其添加到 l:

from itertools import combinations
def pair_up(arr):
    return list(combinations(arr,2))
for x in d.values():
    if len(x)==1: #you don't have to worry about elements that occur only once
        continue 
    else:         # if same element is present at i and j (i<j) then
        l+=pair_up(x) # all pairs of (i,j) are valid (xor(arr[i:j]) = 0)

P.S ：您不必担心排序问题，因为 d 中的所有值显然都会被排序。希望这可以帮助。投票。干杯！

编辑：

代码复杂度：O(n*((xorArr中频率最大的元素的频率)选择2))或O(n*(max_freq C 2)).

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

How to find all the subarrays with xor 0?

arrays

algorithm

bit-manipulation

xor

bitwise-xor