Étant donné deux séquences, trouver le chevauchement maximal entre la fin de l'un et le début de l'autre

J'ai besoin de trouver un (pseudo) code efficace pour résoudre le problème suivant:

Compte tenu de deux séquences de (pas nécessairement distinctes) entiers (a[1], a[2], ..., a[n])et (b[1], b[2], ..., b[n]), trouver le maximum de dtelle sorte que a[n-d+1] == b[1], a[n-d+2] == b[2]... et a[n] == b[d].

Ce ne sont pas des devoirs, j'ai trouvé cela en essayant de contracter deux tenseurs sur autant de dimensions que possible. Je soupçonne qu'un algorithme efficace existe (peut O(n)- être ?), Mais je ne peux pas trouver quelque chose qui ne l'est pas O(n^2). L' O(n^2)approche serait la boucle évidente dpuis une boucle intérieure sur les articles pour vérifier la condition requise jusqu'à atteindre le maximum d. Mais je soupçonne que quelque chose de mieux que cela est possible.

Vous pouvez utiliser l' algorithme z , un algorithme de temps linéaire ( O (n) ) qui:

Étant donné une chaîne S de longueur n, l'algorithme Z produit un tableau Z où Z [i] est la longueur de la plus longue sous-chaîne à partir de S [i] qui est également un préfixe de S

Vous devez concaténer vos tableaux ( b + a ) et exécuter l'algorithme sur le tableau construit résultant jusqu'au premier i tel que Z [i] + i == m + n .

Par exemple, pour a = [1, 2, 3, 6, 2, 3] & b = [2, 3, 6, 2, 1, 0], la concaténation serait [2, 3, 6, 2, 1 , 0, 1, 2, 3, 6, 2, 3] ce qui donnerait Z [10] = 2 satisfaisant Z [i] + i = 12 = m + n .

Pour la complexité temps / espace O (n), l'astuce consiste à évaluer les hachages pour chaque sous-séquence. Considérez le tableau b:

[b1 b2 b3 ... bn]

En utilisant la méthode de Horner , vous pouvez évaluer tous les hachages possibles pour chaque sous-séquence. Choisissez une valeur de base B(supérieure à toute valeur dans vos deux tableaux):

from b1 to b1 = b1 * B^1
from b1 to b2 = b1 * B^1 + b2 * B^2
from b1 to b3 = b1 * B^1 + b2 * B^2 + b3 * B^3
...
from b1 to bn = b1 * B^1 + b2 * B^2 + b3 * B^3 + ... + bn * B^n

Notez que vous pouvez évaluer chaque séquence en temps O (1), en utilisant le résultat de la séquence précédente, d'où tous les coûts de travail O (n).

Vous avez maintenant un tableau Hb = [h(b1), h(b2), ... , h(bn)], où Hb[i]est le hachage de b1jusqu'à bi.

Faites la même chose pour le tableau a, mais avec une petite astuce:

from an to an   =  (an   * B^1)
from an-1 to an =  (an-1 * B^1) + (an * B^2)
from an-2 to an =  (an-2 * B^1) + (an-1 * B^2) + (an * B^3)
...
from a1 to an   =  (a1   * B^1) + (a2 * B^2)   + (a3 * B^3) + ... + (an * B^n)

Vous devez noter que lorsque vous passez d'une séquence à une autre, vous multipliez toute la séquence précédente par B et ajoutez la nouvelle valeur multipliée par B. Par exemple:

from an to an =    (an   * B^1)

for the next sequence, multiply the previous by B: (an * B^1) * B = (an * B^2)
now sum with the new value multiplied by B: (an-1 * B^1) + (an * B^2) 
hence:

from an-1 to an =  (an-1 * B^1) + (an * B^2)

Vous avez maintenant un tableau Ha = [h(an), h(an-1), ... , h(a1)], où Ha[i]est le hachage de aijusqu'à an.

Maintenant, vous pouvez comparer Ha[d] == Hb[d]toutes les dvaleurs de n à 1, si elles correspondent, vous avez votre réponse.

ATTENTION : il s'agit d'une méthode de hachage, les valeurs peuvent être grandes et vous devrez peut-être utiliser une méthode d'exponentiation rapide et une arithmétique modulaire , qui peuvent (à peine) vous donner des collisions , ce qui rend cette méthode pas totalement sûre. Une bonne pratique consiste à choisir une base Bcomme un très grand nombre premier (au moins plus grand que la plus grande valeur de vos tableaux). Vous devez également faire attention car les limites des nombres peuvent déborder à chaque étape, vous devrez donc utiliser (modulo K) dans chaque opération (où Kpeut être un nombre premier plus grand que B).

Cela signifie que deux séquences différentes peuvent avoir le même hachage, mais deux séquences égales auront toujours le même hachage.

Cela peut en effet se faire en temps linéaire, O (n) et O (n) espace supplémentaire. Je suppose que les tableaux d'entrée sont des chaînes de caractères, mais ce n'est pas essentiel.

Une méthode naïve rechercherait - après avoir fait correspondre k caractères égaux - un caractère qui ne correspond pas, et reculerait de k-1 unités dans a , réinitialiser l'index en b , puis démarrer le processus de correspondance à partir de là. Cela représente clairement le pire des cas O (n²) .

Pour éviter ce processus de retour en arrière, nous pouvons observer que revenir en arrière n'est pas utile si nous n'avons pas rencontré le caractère b [0] lors du balayage des k-1 derniers caractères. Si nous avons fait constater que le caractère, retours en arrière alors à cette position ne serait utile, si ce k sized substring nous avons eu une répétition périodique.

Par exemple, si nous regardons la sous-chaîne "abcabc" quelque part dans a , et b est "abcabd", et que nous constatons que le caractère final de b ne correspond pas, nous devons considérer qu'une correspondance réussie peut commencer au deuxième "a" dans la sous-chaîne, et nous devons déplacer notre indice actuel en b en conséquence avant de poursuivre la comparaison.

L'idée est alors de faire un prétraitement basé sur la chaîne b pour enregistrer les références arrières dans b qui sont utiles pour vérifier quand il y a un décalage. Ainsi, par exemple, si b est "acaacaacd", nous pourrions identifier ces références arrières basées sur 0 (placées sous chaque caractère):

index: 0 1 2 3 4 5 6 7 8
b:     a c a a c a a c d
ref:   0 0 0 1 0 0 1 0 5

Par exemple, si nous avons un égal à "acaacaaca", le premier décalage se produit sur le caractère final. Les informations ci-dessus indiquent ensuite à l'algorithme de revenir en b à l'index 5, car "acaac" est courant. Et puis, en ne changeant que l'indice actuel dans b, nous pouvons continuer l'appariement à l'indice actuel de a . Dans cet exemple, la correspondance du dernier caractère réussit.

Avec cela, nous pouvons optimiser la recherche et nous assurer que l'index dans un peut toujours avancer.

Voici une implémentation de cette idée en JavaScript, en utilisant uniquement la syntaxe la plus basique de ce langage:

function overlapCount(a, b) {
    // Deal with cases where the strings differ in length
    let startA = 0;
    if (a.length > b.length) startA = a.length - b.length;
    let endB = b.length;
    if (a.length < b.length) endB = a.length;
    // Create a back-reference for each index
    //   that should be followed in case of a mismatch.
    //   We only need B to make these references:
    let map = Array(endB);
    let k = 0; // Index that lags behind j
    map[0] = 0;
    for (let j = 1; j < endB; j++) {
        if (b[j] == b[k]) {
            map[j] = map[k]; // skip over the same character (optional optimisation)
        } else {
            map[j] = k;
        }
        while (k > 0 && b[j] != b[k]) k = map[k]; 
        if (b[j] == b[k]) k++;
    }
    // Phase 2: use these references while iterating over A
    k = 0;
    for (let i = startA; i < a.length; i++) {
        while (k > 0 && a[i] != b[k]) k = map[k];
        if (a[i] == b[k]) k++;
    }
    return k;
}

console.log(overlapCount("ababaaaabaabab", "abaababaaz")); // 7

Bien qu'il existe des whileboucles imbriquées , celles-ci n'ont pas plus d'itérations au total que n . En effet, la valeur de k diminue strictement dans le whilecorps et ne peut pas devenir négative. Cela ne peut se produire que si a k++été exécuté autant de fois pour donner suffisamment de place à de telles diminutions. Donc, dans l'ensemble, il ne peut y avoir plus d'exécutions du whilecorps qu'il n'y a d' k++exécutions, et ce dernier est clairement O (n).

Pour terminer, vous pouvez trouver ici le même code que ci-dessus, mais dans un extrait interactif: vous pouvez saisir vos propres chaînes et voir le résultat de manière interactive:

function overlapCount(a, b) {
    // Deal with cases where the strings differ in length
    let startA = 0;
    if (a.length > b.length) startA = a.length - b.length;
    let endB = b.length;
    if (a.length < b.length) endB = a.length;
    // Create a back-reference for each index
    //   that should be followed in case of a mismatch.
    //   We only need B to make these references:
    let map = Array(endB);
    let k = 0; // Index that lags behind j
    map[0] = 0;
    for (let j = 1; j < endB; j++) {
        if (b[j] == b[k]) {
            map[j] = map[k]; // skip over the same character (optional optimisation)
        } else {
            map[j] = k;
        }
        while (k > 0 && b[j] != b[k]) k = map[k]; 
        if (b[j] == b[k]) k++;
    }
    // Phase 2: use these references while iterating over A
    k = 0;
    for (let i = startA; i < a.length; i++) {
        while (k > 0 && a[i] != b[k]) k = map[k];
        if (a[i] == b[k]) k++;
    }
    return k;
}

// I/O handling

let [inputA, inputB] = document.querySelectorAll("input");
let output = document.querySelector("pre");

function refresh() {
    let a = inputA.value;
    let b = inputB.value;
    let count = overlapCount(a, b);
    let padding = a.length - count;
    // Apply some HTML formatting to highlight the overlap:
    if (count) {
        a = a.slice(0, -count) + "<b>" + a.slice(-count) + "</b>";
        b = "<b>" + b.slice(0, count) + "</b>" + b.slice(count);
    }
    output.innerHTML = count + " overlapping characters:\n" + 
                         a + "\n" + 
                         " ".repeat(padding) + b;
}

document.addEventListener("input", refresh);
refresh();

body { font-family: monospace }
b { background:yellow }
input { width: 90% }

a: <input value="acacaacaa"><br>
b: <input value="acaacaacd"><br>
<pre></pre>