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

Question

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

例如，如果数组包含元素[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] 的 XOR 等于 XOR 时，子数组 array[i:j] 的 XOR 为零数组[:j]。对于数组的每个后续元素，我们计算以该元素结尾的前缀与以前一个元素结尾的前缀的异或，然后查找上述等式的所有解 i .然后我们插入新的关联并继续。