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>
b[1] to b[d]a następnie przejdź do tablicyahash obliczenia,a[1] to a[d]jeśli to pasuje, to twoja odpowiedź, jeśli nie, oblicz hasha[2] to a[d+1]przez ponowne użycie obliczonego skrótua[1] to a[d]. Ale nie wiem, czy obiekty w tablicy są podatne na obliczanie na nich zmiennego kroczącego.