Căutări în șiruri

Intuiția

Ai un text (de exemplu abracadabra) și un șablon (de exemplu abra), și vrei să afli unde apare șablonul în text. Ideea de bază e simplă: așezi șablonul peste text începând de la poziția 0, verifici caracter cu caracter, apoi îl glisezi o poziție la dreapta și încerci din nou. Faci asta la fiecare poziție posibilă de start. Acolo unde toate caracterele șablonului coincid cu textul, ai găsit o apariție.

Vezi cum funcționează

Urmărește cum șablonul abra alunecă peste textul abracadabra: la fiecare poziție se aliniază și compară litere; la prima nepotrivire sare mai departe, iar când toate coincid marchează o apariție.

Algoritmul pas cu pas

Fie textul abracadabra (lungime n=11) și șablonul abra (lungime m=4). Indexăm de la 0. Pozițiile de start posibile sunt i = 0, 1, ..., n-m = 7.

i=0: comparăm a=a, b=b, r=r, a=a — toate cele 4 coincid. Apariție la poziția 0.

i=1: text[1]='b' vs sablon[0]='a' — nepotrivire din prima. Sărim. i=2: text[2]='r' vs 'a' — nepotrivire. Sărim. i=3: text[3]='a' se potrivește, dar text[4]='c' vs sablon[1]='b' — eșec la al doilea caracter. i=4: text[4]='c' vs 'a' — nepotrivire. i=5: text[5]='a' ok, dar text[6]='d' vs 'b' — eșec la al doilea. i=6: text[6]='d' vs 'a' — nepotrivire.

Toate pozițiile i=1..6 eșuează repede — de obicei chiar la primul caracter.

i=7: comparăm a=a, b=b, r=r, a=a — toate coincid. Apariție la poziția 7.

Implementare C++

Mai jos, căutarea naivă scrisă explicit cu două bucle. Afișează toate pozițiile de start unde apare șablonul.

#include <iostream>
#include <string>
using namespace std;

int main() {
    string text = "abracadabra";   // n = 11
    string sablon = "abra";        // m = 4
    int n = text.size();
    int m = sablon.size();

    // i porneste doar pana la n-m: mai departe sablonul nu mai incape
    for (int i = 0; i <= n - m; i++) {
        int j = 0;
        // compar caracter cu caracter; ies la prima nepotrivire
        while (j < m && text[i + j] == sablon[j]) {
            j++;
        }
        // daca am parcurs tot sablonul, e potrivire la pozitia i
        if (j == m) {
            cout << i << " ";   // afiseaza: 0 7
        }
    }
    return 0;
}

Aceeași căutare, mult mai scurt, cu string::find într-o buclă. find întoarce poziția primei apariții de la un punct dat, sau string::npos dacă nu mai există:

#include <iostream>
#include <string>
using namespace std;

int main() {
    string text = "abracadabra";
    string sablon = "abra";

    // caut de la pozitia urmatoare dupa fiecare gasire
    size_t poz = text.find(sablon, 0);
    while (poz != string::npos) {
        cout << poz << " ";          // afiseaza: 0 7
        poz = text.find(sablon, poz + 1);
    }
    return 0;
}

Ambele variante afișează 0 7 — exact pozițiile găsite în trace.

Complexitate

Pentru fiecare dintre cele n-m+1 poziții de start poți compara până la m caractere, deci în cel mai rău caz aproximativ n*m comparații. Pe lângă cele două șiruri de intrare nu folosim memorie suplimentară.