Как найти самый длинный непрерывный подмассив, XOR которого равен 0

Question

Например, учитывая {1,1,2,2}: все значения XOR этих подмассивов равны 0: {1,1}, {2,2}, {1,1,2,2}.Длина самого длинного - 4.

Найдите длину самого длинного подмассива и верните начальный и конечный индексы этого подмассива.

Answer 1

Вычисляет работающий XOR массива, от 0 элементов до всех элементов.В вашем примере:

initial 
segment         XOR
[]              0
[1]             1
[1, 1]          0
[1, 1, 2]       2
[1, 1, 2, 2]    0

Если два работающих значения XOR одинаковы, подрешетка между этими двумя значениями будет XOR до 0.

Создайте две карты, сохраняя первый и последний увиденный XORзначение.Пройдите через них и найдите пару с наибольшей разницей.

В Python:

def continuous_xor(xs):
    xor = 0
    first_seen = {0: 0}
    last_seen = {0: 0}
    for i, x in enumerate(xs):
        xor = xor ^ x
        if xor not in first_seen:
            first_seen[xor] = i+1
        last_seen[xor] = i+1
    return max((last_seen[i]-first_seen[i], first_seen[i], last_seen[i]) for i in last_seen)

print continuous_xor([1, 1, 2, 2])
print continuous_xor([5, 1, 4, 3, 2, 4, 6])

Индексы подмассива имеют стиль Python, включающий начальный индекс и конечныйиндекс является эксклюзивным.

Это выполняется за время O (n), где n - размер входного массива.