如何找到所有xor为0的子数组？ [英] How to find all the subarrays with xor 0?

问题描述

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

The problem is to find all the subarrays of the given array with xor of all its elements equal to zero.

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

For example, if array contains elements [13,8,5,3,3], the solution should give the indices of all subarrays like 0-2, 3-4, 0-4, etc.

问题类似于被问到的问题此处

The question is similar to the one asked here

唯一的区别是，我希望满足等式的所有子数组的索引 A0 xor A1 xor ... xor An = 0

The only difference is that I want the indices of all the subarrays that satisfies the equation A0 xor A1 xor...xor An = 0

推荐答案

这是链接问题的相当简单的扩展。在Python中，

This is a fairly straightforward extension of the linked question. In 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] array [：i] 的XOR等于 array [：j]的XOR时，code>的XOR为零。 code>。对于数组的每个后续元素，我们从在上一个元素结束的前缀的XOR计算在该元素结束的前缀的XOR，然后查找所有解决方案 i 到上式。然后，我们插入新的关联并继续。

As before, the idea is that a subarray array[i:j] has XOR zero if and only if the XOR of array[:i] equals the XOR of array[:j]. For each subsequent element of the array, we compute the XOR of the prefix ending at that element from the XOR of the prefix ending at the previous element, then look up all of the solutions i to the above equation. Then we insert the new association and continue.

这篇关于如何找到所有xor为0的子数组？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！