De ce contează?
Cauți un cuvânt într-o pagină de carte. Pui degetul la primul rând și citești litera cu literă, comparând cu cuvântul căutat. Dacă o literă nu se potrivește, nu te superi: muți degetul cu o poziție mai la dreapta și încerci din nou, de la capăt. Atât face și un calculator când caută un subșir (pattern) într-un text.
Intuiția
Ai un text lung și un pattern scurt pe care vrei să-l găsești în el. Te așezi cu pattern-ul la prima poziție din text și verifici, caracter cu caracter, dacă se potrivește. Dacă da, ai găsit o apariție. Dacă nu, aluneci cu o poziție mai la dreapta și reîncerci de la capăt. Repeți până ajungi atât de aproape de final încât pattern-ul nu mai are loc.
Vezi cum funcționează
Pornește animația și urmărește cum pattern-ul alunecă peste text, o poziție pe rând, comparând caracter cu caracter de fiecare dată. Apoi citește mai jos de ce această idee simplă poate deveni lentă.
Folosește ← și → ca să pășești prin algoritm, sau Redă pentru animație. Observă că la fiecare nepotrivire pattern-ul se mută cu o singură poziție și compararea reîncepe de la prima literă a pattern-ului.
Ideea naivă: pentru fiecare poziție de start din text, încerci să potrivești tot pattern-ul, caracter cu caracter. Dacă toate caracterele se potrivesc, ai găsit o apariție; altfel treci la poziția următoare.
Pe text „aaaa…a” (n caractere) cu pattern „aa…ab” (m caractere), de la aproape fiecare poziție potrivești m-1 litere identice și apoi pici pe ultima. Ai n start-uri, fiecare cu aproape m comparații: O(n·m). La n = 100000 și m = 1000 ajungi la 100 de milioane de comparații, multe dintre ele potriviri parțiale reluate de la zero.
Când apare o nepotrivire, nu ești pe loc gol: ai deja informație din comparațiile reușite de dinainte. Dacă primele litere ale pattern-ului se repetă, poți „sări" mai inteligent în loc să reiei totul de la prima literă.
Pentru concurs, căutarea naivă O(n·m) e des suficientă când n și m sunt mici. Pentru cazuri mari există KMP, care folosește informația din potrivirea parțială și obține O(n+m), fără să reia comparațiile deja făcute.
Algoritmul pas cu pas
Cauți pattern-ul aba în textul ababa. Notăm pozițiile textului de la 0 la 4.
Pattern-ul are m = 3 caractere, textul n = 5, deci start-urile posibile sunt
de la 0 la n - m = 2.
Start i = 0. Aliniezi aba peste primele 3 caractere și compari:
a | b | a | b | a |
0 | 1 | 2 | 3 | 4 |
t=p | t=p | t=p |
Toate trei se potrivesc, deci ai o apariție la poziția 0.
Start i = 1. Aluneci cu o poziție și compari aba cu textul de la poziția 1:
a | b | a | b | a |
0 | 1 | 2 | 3 | 4 |
p[0]=b |
Prima literă (a) nu se potrivește cu b, deci abandonezi imediat acest start.
Start i = 2. Aliniezi aba peste pozițiile 2, 3, 4:
a | b | a | b | a |
0 | 1 | 2 | 3 | 4 |
t=p | t=p | t=p |
Din nou toate trei se potrivesc: apariție la poziția 2.
Cele două potriviri (la 0 și la 2) se suprapun: împart caracterul de la poziția 2. O căutare corectă raportează ambele, nu se oprește la prima. De aceea continui să muți start-ul cu o singură poziție, chiar și după ce ai găsit o apariție.
Implementare C++
#include <iostream>
#include <string>
using namespace std;
int main() {
string text = "ababa";
string pattern = "aba";
int n = text.size();
int m = pattern.size();
// pentru fiecare pozitie de start posibila in text
for (int i = 0; i <= n - m; i++) {
int j = 0;
// potrivim pattern-ul caracter cu caracter
while (j < m && text[i + j] == pattern[j]) {
j++;
}
// daca am ajuns la capatul pattern-ului, e potrivire completa
if (j == m) {
cout << i << " ";
}
}
// gasit la 0 si 2
return 0;
}În practică, biblioteca standard oferă text.find(pattern), care întoarce prima
poziție a unei apariții (sau string::npos dacă nu există). E util când vrei doar
prima potrivire; pentru toate pozițiile, reaplici find cu un start mutat sau scrii
bucla naivă de mai sus.
Complexitate
| Caz | Timp | Spațiu |
|---|---|---|
| Naiv (mediu) | O(n·m) | O(1) |
| Naiv (cel mai rău) | O(n·m) | O(1) |
| KMP | O(n+m) | O(m) |
Pentru n și m mici (cuvinte scurte, texte de câteva mii de caractere) naivul
trece fără probleme. Când produsul n·m devine mare (text și pattern lungi),
treci la KMP, care obține O(n+m).
Prima capcană: depășești marginile textului la text[i + j]. Dacă lași start-ul
i să meargă până la n - 1 în loc de n - m, pentru j apropiat de m
accesezi în afara textului. Limita corectă este i de la 0 la n - m.
A doua capcană: te oprești la prima potrivire și ratezi pozițiile suprapuse.
Pe aba în ababa, dacă ieși după ce găsești poziția 0, pierzi poziția 2.
Continuă să muți start-ul cu o singură poziție până la final.