Comment trouver tous les sous-tableaux avec xor 0?

Si vous avez deux préfixes différents du tableau avec xor égal, disons préfixe de longueur x1 et préfixe de longueur x2, alors le sous-tableau de x1 + 1 à x2 a xor égal à 0. Créez un dictionnaire (BST, table de hachage , quelque chose de similaire) et y stocker des paires (valeur de la somme des préfixes, préfixes qui donne cette valeur). Deux éléments avec la même valeur vous donnent un sous-tableau. Vous pouvez également le trouver en utilisant Trie si vous le souhaitez.

Utilisation de Trie:

Au début, Trie se compose d'un seul nœud et pas d'arêtes. Nous voulons y ajouter des chiffres. Il serait également pratique de les indexer, car nous voulons trouver tous les sous-tableaux. Chaque nœud qui représente des nombres (multiples en cas de doublons) dans Trie stockera la liste de leurs index, afin que nous puissions facilement obtenir les sous-tableaux.

Lorsque nous ajoutons un nombre n avec un index i, nous écrivons n comme un nombre binaire. Nous partons du nœud initial. Si le bit le plus significatif de n est égal à 0, s'il existe une arête étiquetée 0 à partir de notre départ, nous nous déplaçons vers un sommet correspondant, sinon nous créons une nouvelle arête étiquetée 0 pointant vers un nouveau nœud, nous passons à ce nouveau un (même chose pour 1). Ensuite, nous continuons à faire cela jusqu'à ce que nous ayons parcouru chaque bit de n. Nous ajoutons l'index i à une liste d'indices dans un nœud dans lequel nous nous sommes retrouvés.

1. Rendre la variable prefsum = 0
2. Pour chaque i = 1 à n:
   • ajouter prefsum à Trie avec l'index i
   • set prefsum = prefsum ^ array [i]
   • vérifie s'il existe une valeur prefsum dans Trie. Pour chacune de ces valeurs v, le sous-tableau de x ou égal à 0 est entre les indices v-ème et i-ème.

La complexité totale est O (n * log (valeur maximale dans le tableau))

Ce n'est peut-être pas mieux que d'utiliser BST ou un tableau de hachage, mais c'est une astuce populaire qui brille particulièrement dans certains problèmes avec l'opération XOR.

Il s'agit d'une extension assez simple de la question liée. En 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)

Comme précédemment, l'idée est qu'un sous-tableau array [i: j] a XOR zéro si et seulement si le XOR du array [: i] est égal au XOR du array [: j] . Pour chaque élément suivant du tableau, nous calculons le XOR du préfixe se terminant à cet élément à partir du XOR du préfixe se terminant à l'élément précédent, puis recherchons toutes les solutions i à l'équation ci-dessus . Ensuite, nous insérons la nouvelle association et continuons.

Si vous souhaitez modifier la réponse mentionnée dans l'article, j'espère que vous avez très bien compris cette solution. Maintenant, la chose qui manque dans cette solution est qu'elle ne stocke que la première occurrence d'index d'un préfixe particulier xor sum. Les autres index contenant le même xorSum ne sont pas suivis. Donc ce que vous devez faire est de modifier la carte pour garder une liste (vecteur en C ++) d'index pour chaque xorSum.

J'écrirai les blocs de code en Python 3.7

Soit l une liste de tuples de (i, j)

Le moyen le plus efficace et le plus simple de résoudre le problème est: p >

Étape 1: calculez le xor des préfixes:

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)

Étape 2: Vérifiez si à tout moment xorArr [i] = 0, si oui alors arr [: i +1] est un sous-tableau dont le xor est nul:

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]

Étape 3: Maintenant, créez un dictionnaire pour stocker la liste des index de chaque élément apparaissant dans xorArr

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

Étape 4: Créez une fonction qui appairera (i, j) pour chaque élément de d [xorArr [x]] et ajoutez-la à l:

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