De ce contează?
Cauți un cuvânt într-o pagină. Când potrivirea se strică după câteva litere, instinctul zice „ia-o de la capăt de la litera următoare". Dar dacă începutul cuvântului tău s-a mai potrivit puțin, nu trebuie să arunci tot. Tabela next îți spune exact cât poți păstra din ce ai potrivit deja, ca să nu pornești mereu de la zero.
Intuiția
Cauți șablonul într-un text, literă cu literă. Când o literă nu se potrivește, naivul o ia de la capăt: dă înapoi în text și reîncepe șablonul. Ideea-cheie e că prefixul deja potrivit din șablon poate fi, în același timp, și sufixul lui — iar atunci o parte din el e deja aliniată corect. Tabela next măsoară, pentru fiecare poziție, cât din acel prefix poți reutiliza. Cu ea avansezi mereu în text, fără să dai vreodată înapoi.
Vezi cum funcționează
Pornește animația și urmărește cum șablonul alunecă peste text, comparat literă cu literă. La fiecare nepotrivire, vizualizarea îți arată cum se reia compararea.
Folosește ← și → ca să pășești comparație cu comparație, sau Redă pentru animație. Vizualizarea arată potrivirea șablon–text caracter cu caracter; trucul KMP e că, în loc să mute textul înapoi la fiecare ratare, folosește tabela next ca să nu dea niciodată înapoi în text.
Căutare naivă: pui șablonul la începutul textului și compari literă cu literă. La prima nepotrivire muți șablonul cu o poziție mai la dreapta și reîncepi de la prima lui literă — dând înapoi în text. În cel mai rău caz faci O(n*m) comparații.
Ia un text mare de un milion de litere și un șablon care se potrivește parțial de multe ori (multe prefixe comune). De fiecare dată ai potrivit zeci de litere, apoi pici și reiei totul de la capăt. Pentru n = m = 100000 ajungi la ordinul a 10^10 comparații — mult peste o secundă de concurs.
Când potrivirea se rupe după ce ai potrivit deja un prefix al șablonului, acel prefix poate fi și sufix al lui — deci o bucată din el e deja aliniată cu textul. Tabela next îți spune exact cât poți păstra, ca să nu reîncepi de la zero și să nu dai înapoi în text.
Precalculezi tabela next a șablonului (o singură trecere prin el), apoi cauți cu o
singură trecere prin text: la fiecare nepotrivire sari în șablon la next[k-1],
iar indicele din text nu se întoarce niciodată. Total: O(n+m) timp.
Algoritmul pas cu pas
Fie șablonul a b a b c. Tabela next are câte o valoare pentru fiecare poziție:
next[i] = lungimea celui mai lung prefix propriu al șablonului care e în același
timp și sufix în sablon[0..i].
a | b | a | b | c |
0 | 1 | 2 | 3 | 4 |
0 | 0 | 1 | 2 | 0 |
0 | 1 | 2 | 3 | 4 |
Cum verifici valorile, poziție cu poziție:
next[0] = 0: o singură literă nu are prefix propriu.next[1] = 0: înab, prefixulanu se potrivește cu sufixulb.next[2] = 1: înaba, prefixulae și sufix → 1.next[3] = 2: înabab, prefixulabreapare ca sufix → 2.next[4] = 0: înababcnimic nu se repetă (se termină înc) → 0.
Acum caută ababc în textul a b a b a b c. Potrivești abab (4 litere), apoi
text[4] = a ratează față de sablon[4] = c. În loc să dai înapoi în text, sari
în șablon la next[3] = 2: păstrezi prefixul ab deja aliniat și continui de la
sablon[2].
a | b | a | b | a | b | c |
0 | 1 | 2 | 3 | 4 | 5 | 6 |
i |
De la next[3] = 2 compari text[4]=a cu sablon[2]=a (se potrivește, k=3),
apoi text[5]=b cu sablon[3]=b (k=4), apoi text[6]=c cu sablon[4]=c (k=5 = m).
Potrivire găsită, care începe la indicele 6 - 5 + 1 = 2 din text.
next[i] = lungimea celui mai lung prefix care e și sufix în sablon[0..i]. Când
potrivirea se rupe după k litere potrivite, sari în șablon la next[k-1] și
păstrezi exact acel prefix — fără să muți vreodată indicele din text înapoi.
Implementare C++
Întâi construiești tabela next a șablonului, apoi cauți o singură dată prin text folosind-o.
#include <iostream>
#include <string>
using namespace std;
int main() {
string text = "abababc";
string sablon = "ababc";
int n = text.size();
int m = sablon.size();
// next[i] = cel mai lung prefix care e si sufix in sablon[0..i]
int next[1005];
next[0] = 0;
int k = 0; // lungimea prefixului-sufix curent
for (int i = 1; i < m; i++) {
// cat timp nu se potriveste, dau inapoi pe valoarea next anterioara
while (k > 0 && sablon[i] != sablon[k]) {
k = next[k - 1];
}
if (sablon[i] == sablon[k]) {
k++;
}
next[i] = k;
}
// pentru ababc: next = 0 0 1 2 0
// cautarea: o singura trecere prin text, fara sa dau inapoi in i
k = 0; // cate litere din sablon am potrivit deja
for (int i = 0; i < n; i++) {
// la nepotrivire sar in sablon la next[k-1], NU dau inapoi in text
while (k > 0 && text[i] != sablon[k]) {
k = next[k - 1];
}
if (text[i] == sablon[k]) {
k++;
}
if (k == m) {
// potrivire completa care se termina pe pozitia i
cout << "Gasit la pozitia " << i - m + 1 << "\n"; // 2
k = next[k - 1]; // continui sa caut urmatoarea aparitie
}
}
return 0;
}Complexitate
| Caz | Timp | Spațiu |
|---|---|---|
| Mediu și cel mai rău | O(n + m) | O(m) |
Construcția tabelei next costă O(m), iar căutarea O(n): fiecare literă din text e
privită o singură dată, iar k nu poate scădea mai mult decât a crescut.
Capcana clasică: când potrivirea se rupe, dai înapoi cu o singură poziție în
loc să folosești tabela next. Corect e să sari la next[k-1] — exact cât din
prefix mai rămâne valid. A doua greșeală, și mai gravă: să muți indicele din text
înapoi. În KMP nu dai niciodată înapoi în text; doar k (poziția în șablon)
scade, iar i doar crește.