Căutări în șiruri — unde apare un tipar

De ce contează?

Când folosești Ctrl+F într-un document ca să găsești un cuvânt, calculatorul plimbă tiparul căutat de-a lungul textului și verifică, poziție cu poziție, dacă se potrivește. Căutarea unui subșir face exact asta.

Problema

Ai un text s și un tipar t. Vrei să afli dacă (și unde) apare t în s. Exemplu: tiparul "ana" apare în textul "banana" la poziția 1 și la poziția 3.

Căutarea naivă, pas cu pas

Încerci fiecare poziție de start din text. Pentru fiecare, verifici dacă tiparul se potrivește, caracter cu caracter. Fie s = "banana", t = "ana":

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

Textul în care căutăm tiparul „ana”.

start 0: b vs a → nu
start 1: a n a vs a n a → potrivire la poziția 1
start 2: n vs a → nu
start 3: a n a vs a n a → potrivire la poziția 3

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

Prima potrivire: „ana” aliniat la indexul 1.

Implementare C++ (naiv)

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

int cautaPrima(string s, string t) {
    int n = s.size(), m = t.size();
    for (int start = 0; start + m <= n; start++) {   // pozitii de start valide
        int k = 0;
        while (k < m && s[start + k] == t[k]) k++;   // potrivim caracter cu caracter
        if (k == m) return start;                    // tot tiparul a corespuns
    }
    return -1;                                       // negasit
}

int main() {
    cout << cautaPrima("banana", "ana") << "\n";  // 1
    cout << cautaPrima("banana", "xyz") << "\n";  // -1
    return 0;
}

De ce start + m <= n? Dacă tiparul de lungime m ar începe mai târziu, ar ieși din text. Condiția te ține în zona unde potrivirea e posibilă.

Observația-cheie

Verificarea internă se oprește la prima diferență (while-ul iese imediat). De aceea, în practică, naivul e adesea rapid — dar în cel mai rău caz (ex. s = "aaaa...a", t = "aaa...b") face O(n · m) comparații.

Soluția din bibliotecă: find

În concursuri, când nu ai nevoie de algoritm propriu, folosește find:

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

int main() {
    string s = "banana", t = "ana";
    size_t poz = s.find(t);
    if (poz != string::npos) cout << "prima la " << poz << "\n";  // 1

    // numara TOATE aparitiile (cu suprapuneri)
    int total = 0;
    size_t p = s.find(t);
    while (p != string::npos) {
        total++;
        p = s.find(t, p + 1);   // reia de la p+1 pentru suprapuneri
    }
    cout << total << "\n";      // 2
    return 0;
}

Observația-cheie

Pentru apariții care se pot suprapune ("aa" în "aaa" apare de 2 ori), reia căutarea de la p + 1. Dacă vrei doar apariții disjuncte, reia de la p + t.size().

Complexitate

Metodă	Timp (cel mai rău)	Spațiu
Căutare naivă	O(n · m)	O(1)
`s.find`	O(n · m)	O(1)
(avansat) KMP, mai târziu	O(n + m)	O(m)

Greșeli frecvente

Greșeli frecvente de concurs:

find comparat cu -1: rezultatul e fără semn; testează == string::npos.
Buclă infinită la numărare: dacă reiei căutarea de la p (nu p + 1), găsești la nesfârșit aceeași poziție.
Condiție de start greșită: start < n în loc de start + m <= n accesează în afara textului la final.
Limită de timp: pentru n mare și multe potriviri parțiale, naivul O(n·m) poate depăși timpul; atunci ai nevoie de un algoritm O(n + m) (KMP).

Vizualizare

Indiciu

Urmărește cum tiparul alunecă și unde apar nepotrivirile; folosește ← / → pentru a avansa pas cu pas.

Recapitulare

Căutarea naivă încearcă fiecare poziție de start și potrivește caracter cu caracter — simplu, O(n · m) în cel mai rău caz.
s.find(t) întoarce prima poziție sau string::npos; reia de la p + 1 pentru a număra apariții suprapuse.
Pentru texte mari cu multe potriviri parțiale, algoritmii O(n + m) (KMP) devin necesari.