Calcul du mode des sous-séquences XOR

Question

J'ai été confronté à ce problème lors d'un challenge de programmation en ligne et cela me dérange depuis :

Dans le problème, on vous donne une liste de numéros 16 bits, disons $ a_0, a_1, ..., a_n $.Une « sous-séquence XOR » est définie comme la combinaison ou exclusif de chaque élément d'une sous-séquence consécutive de la liste.Le problème est que vous devez trouver la sous-séquence XOR la ​​plus courante parmi toutes les sous-séquences consécutives possibles dans la liste.En cas d'égalité, la valeur numérique XOR la ​​plus basse parmi les plus fréquentes l'emporte.

La première solution que j'ai proposée était une solution $O(n^2)$ dans laquelle je calcule le XOR pour les sous-séquences consécutives $a_0,...,a_i$ de $i=0$ à $i=n$, ce qui peut être fait dans $O(n)$, et faire la même chose en commençant à $a_1$, etc., et en incrémentant un compteur dans une carte pour chaque résultat.Je sais que cela répète beaucoup de travail, j'ai donc abordé le problème sous un angle différent et essayé de le définir mathématiquement.J'ai défini $X_{i,j}$ comme étant le XOR de $a_i,...,a_j$ afin de pouvoir écrire ce qui suit :

$ X_ {i, j} = begin {case} a_i & text {if} i = j a_j oplus x_ {0, j-1} & text {if} i = 0 text {et} j> 0 x_ {0, i-1} oplus x_ {0, j} & text {if} 0 <i <j end {cas} $

J'ai implémenté cela avec la mémorisation, qui, je crois, élimine tous les calculs redondants, mais l'utilisation de la mémorisation s'avère lente et utilise l'espace $O(n^2)$ lorsque vous tentez de calculer tous les $X_{i,j}$ pour $0 \leq i \leq n $ et $i \leq j \leq n$, ce qui est inacceptable.

Existe-t-il un moyen de rendre cela plus rapide que $O(n^2)$ ?Ou sinon, existe-t-il un moyen efficace de réduire le nombre de calculs ?Ou est-ce que je manque une simplification du problème qui ne m'oblige pas à calculer chaque $X_{i,j}$ ?Je suis en quelque sorte nouveau dans la programmation dynamique, il a donc été difficile de comprendre ce problème.Ma solution originale était trop lente d'un facteur d'environ 5 secondes (par rapport au délai de 4 secondes pour le défi), donc je pense que même une réduction constante du temps rendrait la solution acceptable.