Biorąc pod uwagę dwie sekwencje, znajdź maksymalne nakładanie się między końcem jednego a początkiem drugiego

Muszę znaleźć wydajny (pseudo) kod, aby rozwiązać następujący problem:

Biorąc pod uwagę dwie sekwencje (niekoniecznie różnych) liczb całkowitych (a[1], a[2], ..., a[n])i (b[1], b[2], ..., b[n])znajdź maksymalna dtakie, że a[n-d+1] == b[1], a[n-d+2] == b[2], ..., i a[n] == b[d].

To nie jest praca domowa, właściwie to wymyśliłem, próbując skurczyć dwa tensory wzdłuż możliwie największej liczby wymiarów. Podejrzewam, że istnieje skuteczny algorytm (może O(n)?), Ale nie mogę wymyślić czegoś, co nie jest O(n^2). O(n^2)Podejście byłoby oczywistym pętla na dczym wewnętrzna pętla na pozycje do sprawdzenia stanu wymaganego momentu trafienia maksimum d. Ale podejrzewam, że możliwe jest coś lepszego niż to.

Możesz użyć algorytmu z, algorytmu czasu liniowego ( O (n) ), który:

Biorąc pod uwagę ciąg S o długości n, algorytm Z tworzy tablicę Z, gdzie Z [i] jest długością najdłuższego podłańcucha zaczynając od S [i], który jest również prefiksem S

Musisz połączyć swoje tablice ( b + a ) i uruchomić algorytm na wynikowej skonstruowanej tablicy do pierwszego i takiego, że Z [i] + i == m + n .

Na przykład dla a = [1, 2, 3, 6, 2, 3] i b = [2, 3, 6, 2, 1, 0] konkatenacja wynosiłaby [2, 3, 6, 2, 1 , 0, 1, 2, 3, 6, 2, 3], co dałoby Z [10] = 2 spełniające Z [i] + i = 12 = m + n .

W przypadku złożoności czasowej / przestrzennej O (n) sztuczka polega na ocenie skrótów dla każdej podsekwencji. Rozważ tablicę b:

[b1 b2 b3 ... bn]

Za pomocą metody Hornera możesz ocenić wszystkie możliwe wartości skrótu dla każdej podsekwencji. Wybierz wartość podstawową B(większą niż dowolna wartość w obu twoich tablicach):

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

Zauważ, że możesz ocenić każdą sekwencję w czasie O (1), korzystając z wyniku poprzedniej sekwencji, stąd wszystkie koszty pracy O (n).

Teraz masz tablicę Hb = [h(b1), h(b2), ... , h(bn)], gdzie Hb[i]jest skrót od b1do bi.

Zrób to samo dla tablicy a, ale z małą sztuczką:

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)

Należy pamiętać, że przechodząc z jednej sekwencji do drugiej, mnożymy całą poprzednią sekwencję przez B i dodajemy nową wartość pomnożoną przez B. Na przykład:

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)

Teraz masz tablicę Ha = [h(an), h(an-1), ... , h(a1)], gdzie Ha[i]jest skrót od aido an.

Teraz możesz porównać Ha[d] == Hb[d]dla wszystkich dwartości od n do 1, jeśli pasują, masz odpowiedź.

UWAGA : jest to metoda mieszania, wartości mogą być duże i może być konieczne użycie szybkiej metody potęgowania i arytmetyki modułowej , która może (z trudem) powodować kolizje , dzięki czemu ta metoda nie jest całkowicie bezpieczna. Dobrą praktyką jest wybranie bazy Bjako naprawdę dużej liczby pierwszej (przynajmniej większej niż największa wartość w twoich tablicach). Powinieneś także uważać, ponieważ limity liczb mogą przepełniać się na każdym kroku, więc będziesz musiał używać (modulo K) w każdej operacji (gdzie liczba Kpierwsza może być większa niż B).

Oznacza to, że dwie różne sekwencje mogą mieć ten sam skrót, ale dwie równe sekwencje zawsze będą miały ten sam skrót.

Można to rzeczywiście zrobić w czasie liniowym, O (n) i O (n) dodatkowej przestrzeni. Zakładam, że tablice wejściowe są ciągami znaków, ale nie jest to konieczne.

Naiwna metoda - po dopasowaniu k równych znaków - znalazłaby znak, który nie pasuje, i cofnąłaby jednostki k-1 w a , zresetowała indeks wb , a następnie rozpoczęła proces dopasowania. To wyraźnie reprezentuje najgorszy przypadek O (n²) .

Aby uniknąć tego procesu powrotu, możemy zauważyć, że cofnięcie się nie jest przydatne, jeśli nie napotkaliśmy znaku b [0] podczas skanowania ostatnich znaków k-1 . Gdybyśmy zrobili znaleźć ten znak, a następnie wycofywania do tej pozycji byłby tylko przydatny, jeśli w to k sized podciąg mieliśmy okresowe powtarzanie.

Na przykład, jeśli spojrzymy na podciąg „abcabc” gdzieś w a , a b to „abcabd” i stwierdzimy, że końcowy znak b nie pasuje, musimy wziąć pod uwagę, że pomyślne dopasowanie może rozpocząć się od drugiego „a” w podciągu i powinniśmy odpowiednio przenieść nasz bieżący indeks wb przed kontynuowaniem porównania.

Pomysł polega na tym, aby wykonać wstępne przetwarzanie w oparciu o ciąg b, aby zalogować wstecz referencje w b, które są przydatne do sprawdzenia, kiedy występuje niezgodność. Na przykład, jeśli b jest „acaacaacd”, moglibyśmy zidentyfikować te odwołania wsteczne oparte na 0 (umieść poniżej każdego znaku):

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

Na przykład, jeśli mamy wartość równą „acaacaaca”, pierwsze niedopasowanie nastąpi na końcowej postaci. Powyższe informacje każą algorytmowi wrócić do b do indeksu 5, ponieważ „acaac” jest powszechny. A następnie zmieniając tylko bieżący indeks wb , możemy kontynuować dopasowanie przy bieżącym indeksie a . W tym przykładzie dopasowanie ostatniego znaku kończy się powodzeniem.

Dzięki temu możemy zoptymalizować szukanie i upewnij się, że indeks w zawsze może przejść do przodu.

Oto implementacja tego pomysłu w JavaScript, wykorzystująca tylko najbardziej podstawową składnię tego języka:

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

Chociaż istnieją zagnieżdżone whilepętle, nie mają one w sumie więcej iteracji niż n . Jest tak, ponieważ wartość k ściśle zmniejsza się w whileciele i nie może stać się ujemna. Może się to zdarzyć tylko wtedy, gdy k++wykonano go tyle razy, aby dać wystarczająco dużo miejsca na takie obniżki. Podsumowując, nie może być więcej egzekucji whileciała niż k++egzekucje, a ta ostatnia jest wyraźnie O (n).

Aby ukończyć, możesz znaleźć ten sam kod, co powyżej, ale w interaktywnym fragmencie: możesz wprowadzić własne ciągi znaków i interaktywnie zobaczyć wynik:

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>