Bestimmen Sie bei zwei Sequenzen die maximale Überlappung zwischen dem Ende der einen und dem Anfang der anderen

Ich muss einen effizienten (Pseudo-) Code finden, um das folgende Problem zu lösen:

Gegeben seien zwei Sequenzen von (nicht notwendig verschiedenen) ganzen Zahlen (a[1], a[2], ..., a[n])und (b[1], b[2], ..., b[n])finden Sie das Maximum , dso dass a[n-d+1] == b[1], a[n-d+2] == b[2], ... und a[n] == b[d].

Dies sind keine Hausaufgaben, ich habe sie mir tatsächlich ausgedacht, als ich versucht habe, zwei Tensoren in möglichst vielen Dimensionen zusammenzuziehen. Ich vermute, dass es einen effizienten Algorithmus gibt (vielleicht O(n)?), Aber ich kann mir nichts einfallen lassen, was nicht der Fall ist O(n^2). Der O(n^2)Ansatz wäre die offensichtliche Schleife an dund dann eine innere Schleife an den Elementen, um den erforderlichen Zustand zu überprüfen, bis das Maximum erreicht ist d. Aber ich vermute, dass etwas Besseres möglich ist.

Sie können den z-Algorithmus verwenden , einen linearen Zeitalgorithmus ( O (n) ), der:

Wenn ein String S der Länge n gegeben ist, erzeugt der Z-Algorithmus ein Array Z, wobei Z [i] die Länge des längsten Teilstrings ausgehend von S [i] ist, der auch ein Präfix von S ist

Sie müssen Ihre Arrays verketten ( b + a ) und den Algorithmus auf dem resultierenden konstruierten Array bis zum ersten i ausführen, sodass Z [i] + i == m + n .

Zum Beispiel wäre für a = [1, 2, 3, 6, 2, 3] & b = [2, 3, 6, 2, 1, 0] die Verkettung [2, 3, 6, 2, 1 , 0, 1, 2, 3, 6, 2, 3], was Z [10] = 2 ergeben würde, das Z [i] + i = 12 = m + n erfüllt .

Für die O (n) Zeit / Raum-Komplexität besteht der Trick darin, Hashes für jede Teilsequenz auszuwerten. Betrachten Sie das Array b:

[b1 b2 b3 ... bn]

Mit der Horner-Methode können Sie alle möglichen Hashes für jede Teilsequenz auswerten. Wählen Sie einen Basiswert B(größer als jeder Wert in beiden Arrays):

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

Beachten Sie, dass Sie jede Sequenz in O (1) -Zeit anhand des Ergebnisses der vorherigen Sequenz auswerten können, daher alle Auftragskosten O (n).

Jetzt haben Sie ein Array Hb = [h(b1), h(b2), ... , h(bn)], wo Hb[i]ist der Hash von b1bis bi.

Machen Sie dasselbe für das Array a, aber mit einem kleinen Trick:

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)

Sie müssen beachten, dass Sie beim Übergang von einer Sequenz zur nächsten die gesamte vorherige Sequenz mit B multiplizieren und den neuen Wert multipliziert mit B addieren. Beispiel:

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)

Jetzt haben Sie ein Array Ha = [h(an), h(an-1), ... , h(a1)], wo Ha[i]ist der Hash von aibis an.

Jetzt können Sie Ha[d] == Hb[d]für alle dWerte von n bis 1 vergleichen. Wenn sie übereinstimmen, haben Sie Ihre Antwort.

ACHTUNG : Dies ist eine Hash-Methode. Die Werte können groß sein und Sie müssen möglicherweise eine schnelle Exponentiationsmethode und modulare Arithmetik verwenden , die (kaum) zu Kollisionen führen können , wodurch diese Methode nicht vollständig sicher ist. Eine gute Vorgehensweise besteht darin, eine Basis Bals wirklich große Primzahl auszuwählen (zumindest größer als der größte Wert in Ihren Arrays). Sie sollten auch vorsichtig sein, da die Grenzen der Zahlen bei jedem Schritt überlaufen können. Daher müssen Sie Kbei jeder Operation ( Modulo ) verwenden (wobei Keine Primzahl größer sein kann als B).

Dies bedeutet, dass zwei verschiedene Sequenzen möglicherweise denselben Hash haben, aber zwei gleiche Sequenzen immer denselben Hash haben.

Dies kann in der Tat in linearer Zeit, O (n) und O (n) zusätzlichem Raum erfolgen. Ich gehe davon aus, dass die Eingabearrays Zeichenfolgen sind, dies ist jedoch nicht unbedingt erforderlich.

Eine naive Methode würde - nach dem Abgleichen von k Zeichen, die gleich sind - ein Zeichen finden, das nicht übereinstimmt, und k-1 Einheiten in a zurückgehen, den Index in b zurücksetzen und dann den Abgleichprozess von dort aus starten. Dies ist eindeutig ein O (n²) Worst Case.

Um diesen Rückverfolgungsprozess zu vermeiden, können wir feststellen, dass ein Zurückgehen nicht sinnvoll ist, wenn wir beim Scannen der letzten k-1- Zeichen nicht auf das Zeichen b [0] gestoßen sind . Wenn wir haben diesen Charakter finden, dann zu dieser Position Rückzieher wäre nur dann sinnvoll sein, wenn in dem k sized Teilzeichen wir eine periodische Wiederholung haben.

Wenn wir zum Beispiel die Teilzeichenfolge "abcabc" irgendwo in a betrachten und b "abcabd" ist und wir feststellen, dass das endgültige Zeichen von b nicht übereinstimmt, müssen wir berücksichtigen, dass eine erfolgreiche Übereinstimmung möglicherweise beim zweiten "a" beginnt. in der Teilzeichenfolge, und wir sollten unseren aktuellen Index in b entsprechend zurück verschieben, bevor wir den Vergleich fortsetzen.

Die Idee ist dann, eine Vorverarbeitung basierend auf der Zeichenfolge b durchzuführen, um Rückverweise in b zu protokollieren , die nützlich sind, um zu überprüfen, ob eine Nichtübereinstimmung vorliegt. Wenn b beispielsweise "acaacaacd" ist, können wir diese 0-basierten Rückreferenzen identifizieren (unter jedem Zeichen):

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

Zum Beispiel, wenn wir einen gleich „acaacaaca“ der erste Mismatch geschieht auf dem letzten Zeichen. Die obigen Informationen weisen den Algorithmus dann an, in b zu Index 5 zurückzukehren, da "acaac" üblich ist. Und wenn wir nur den aktuellen Index in b ändern, können wir den Abgleich mit dem aktuellen Index von a fortsetzen . In diesem Beispiel ist die Übereinstimmung des letzten Zeichens dann erfolgreich.

Damit können wir die Suche optimieren und sicherstellen, dass der Index in a immer vorwärts gehen kann.

Hier ist eine Implementierung dieser Idee in JavaScript, wobei nur die grundlegendste Syntax dieser Sprache verwendet wird:

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

Obwohl es verschachtelte whileSchleifen gibt, haben diese insgesamt nicht mehr Iterationen als n . Dies liegt daran, dass der Wert von k im whileKörper streng abnimmt und nicht negativ werden kann. Dies kann nur geschehen, wenn dies so k++oft ausgeführt wurde, dass genügend Platz für solche Abnahmen vorhanden ist. Alles in allem kann es also nicht mehr Hinrichtungen des whileKörpers geben als k++Hinrichtungen, und letztere ist eindeutig O (n).

Zum Abschluss finden Sie hier den gleichen Code wie oben, jedoch in einem interaktiven Snippet: Sie können Ihre eigenen Zeichenfolgen eingeben und das Ergebnis interaktiv anzeigen:

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>