Căutări în șiruri — găsește un cuvânt în text

De ce contează?

Cauți cuvântul „algoritm" într-o pagină de carte. Ce faci? Aluneci cu privirea de la început și, la fiecare poziție, verifici dacă de acolo începe cuvântul. Exact așa caută și calculatorul un tipar într-un text: încearcă fiecare poziție de start.

Problema căutării

Ai un text s (lungime n) și un tipar t (lungime m). Vrei să afli dacă t apare în s și, dacă da, de la ce poziție. E baza oricărui „Ctrl+F".

Observația-cheie

Tiparul nu poate începe oriunde: dacă pornește de la o poziție mai mare decât n - m, ultimele lui caractere ar ieși din text. Deci verifici doar pozițiile de start 0 .. n-m.

Algoritmul direct, pas cu pas

Căutăm t = "ana" în s = "banana". Încercăm fiecare poziție de start și comparăm caracter cu caracter:

s	b	a	n	a	n	a
index	0	1	2	3	4	5

Start = 1: s[1..3] = „ana” == t → potrivire găsită la poziția 1.

start=0: s[0]='b' != t[0]='a'  -> esueaza imediat
start=1: 'a'='a', 'n'='n', 'a'='a' -> POTRIVIRE la pozitia 1

Implementare C++ (metoda directă)

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

int cautaTipar(const string& s, const string& t) {
    int n = s.size(), m = t.size();
    for (int start = 0; start + m <= n; start++) {  // doar pozitii valide
        int j = 0;
        while (j < m && s[start + j] == t[j]) {
            j++;
        }
        if (j == m) {
            return start;          // tot tiparul s-a potrivit
        }
    }
    return -1;                     // negasit
}

int main() {
    cout << cautaTipar("banana", "ana") << endl;  // 1
    cout << cautaTipar("banana", "xyz") << endl;  // -1
    return 0;
}

Varianta cu funcția standard

Pentru concursurile de gimnaziu, find rezolvă rapid căutarea simplă:

string s = "banana", t = "ana";
size_t poz = s.find(t);
if (poz != string::npos) {
    cout << poz << endl;          // 1
}
// toate aparitiile:
poz = s.find(t);
while (poz != string::npos) {
    cout << poz << " ";           // 1 3
    poz = s.find(t, poz + 1);
}

Complexitate

Metodă	Timp	Spațiu
Directă (cel mai rău caz)	O(n · m)	O(1)
Directă (text obișnuit)	aproape O(n)	O(1)

Pentru n mare și multe potriviri parțiale există algoritmi în O(n + m) (KMP), dar metoda directă e suficientă și corectă pentru dimensiunile de la gimnaziu.

Greșeli frecvente

Greșeli reale la căutare:

Limita buclei greșită. start < n în loc de start + m <= n → compari în afara textului pe ultimele poziții.
Compari find cu -1. Rezultatul „negăsit" e string::npos (unsigned), nu -1.
Uiți + 1 la apariții multiple. s.find(t, poz) fără +1 găsește la nesfârșit aceeași poziție → buclă infinită.
Numeri suprapunerile greșit. Pentru "aaa" și tiparul "aa", dacă reiei de la poz + m ratezi potrivirea suprapusă de la poziția 1; reia de la poz + 1 dacă vrei toate.

Recapitulare

Căutarea directă încearcă fiecare poziție de start validă (0 .. n-m) și compară pe litere.
find rezolvă rapid; întoarce poziția primei apariții sau string::npos.
Pentru toate aparițiile, reia de la poziție + 1; atenție la potrivirile suprapuse.