Wzorzec w tekście — metoda naiwna

🎯 Po co Ci to?

Ctrl+F. Naciskasz to codziennie: w przeglądarce, w notatkach, w PDF-ach. Po drugiej stronie skrótu pracuje algorytm, który musi znaleźć Twoje słowo w tekście — być może liczącym miliony znaków — zanim zdążysz mrugnąć. Dziś zbudujesz jego najprostszą wersję własnymi rękami. „Naiwna" w nazwie nie jest obelgą: to uczciwy, poprawny algorytm, punkt odniesienia dla wszystkich sprytniejszych — i ulubieniec autorów zadań maturalnych.

✅ Czego się nauczysz

Po tej jednostce potrafisz:

  • zapisać i prześledzić naiwne wyszukiwanie wzorca (okno + porównanie);
  • policzyć koszt: ile porównań w najlepszym i najgorszym przypadku;
  • wskazać, gdzie metoda naiwna wystarcza, a gdzie potrzeba czegoś więcej.

📘 Wyjaśnienie

Problem (specyfikacja!): Dane: tekst $t$ długości $n$ i wzorzec $w$ długości $m$, $m \le n$. Wynik: pozycja (indeks) pierwszego wystąpienia $w$ w $t$ albo informacja, że wzorca nie ma.

Pomysł naiwny: przykładaj wzorzec do tekstu na każdej możliwej pozycji — jak szablon do ściany — i sprawdzaj znak po znaku, czy pasuje:

tekst:    a l a b a m a
wzorzec:  a b a           ← pozycja 0: a✓ l✗ — przesuń
            a b a         ← pozycja 1: l✗ — przesuń
              a b a       ← pozycja 2: a✓ b✓ a✓ — TRAFIONE, pozycja 2

def znajdz(t, w):
    n, m = len(t), len(w)
    for i in range(n - m + 1):         # możliwe pozycje przyłożenia
        zgadza = True
        for j in range(m):             # porównanie znak po znaku
            if t[i + j] != w[j]:
                zgadza = False
                break                  # niezgodność — dalsze porównywanie zbędne
        if zgadza:
            return i                   # pierwsze wystąpienie
    return -1                          # umowny sygnał "nie ma"

Trzy szczegóły warte uwagi. Zakres pozycji: ostatnie sensowne przyłożenie to $i = n - m$ (dalej wzorzec wystaje poza tekst) — stąd range(n - m + 1); pomylisz o jeden i albo zgubisz wystąpienie na końcu, albo wyjedziesz poza napis (IndexError — kłania się 3.4). break przerywa wewnętrzną pętlę przy pierwszej niezgodności — bez sensu porównywać resztę okna, skoro już wiadomo, że nie pasuje. -1 jako „nie ma": indeksy są nieujemne, więc $-1$ jest bezpiecznym sygnałem specjalnym (tak samo robi wbudowane t.find(w) — Twoja funkcja to jego rekonstrukcja).

Ile to kosztuje? Pozycji jest około $n$, w każdej do $m$ porównań — najgorszy przypadek to około $n \cdot m$ operacji. Ale kiedy właściwie jest najgorzej?

💭 Pomyśl: Ułóż tekst i wzorzec, przy których naiwny algorytm naprawdę wykonuje blisko $n \cdot m$ porównań — czyli w każdej pozycji porównuje prawie cały wzorzec, zanim odkryje niezgodność. Podpowiedź: znaki muszą się długo „zgadzać".

Sprawdź odpowiedź

Klasyk: tekst aaaaaaaaaa…a ($n$ znaków „a") i wzorzec aaab (m−1 „a" i „b" na końcu). W każdej pozycji zgadzają się aż trzy „a" — i dopiero czwarte porównanie (b vs a) obala dopasowanie. Porównań: około $n \cdot m$. Teksty „monotonne" (DNA! — cztery litery, długie powtórzenia) to naturalna specjalność tego najgorszego przypadku i powód, dla którego bioinformatyka używa sprytniejszych metod. Dla zwykłego tekstu po polsku niezgodność wypada zwykle na pierwszym–drugim znaku i naiwny działa niemal liniowo.

🧮 Prześledź

Ile dokładnie porównań znaków wykona znajdz("ababab", "abb")? Rozpisz pozycja po pozycji.

Sprawdź odpowiedź

Pozycje $i = 0 \dots 3$. $i=0$: a✓ b✓ b✗(a) — 3 porównania. $i=1$: b✗(a)... uwaga: porównujemy t[1]='b' z w[0]='a' — niezgodność od razu — 1. $i=2$: a✓ b✓ b✗(a) — 3. $i=3$: b✗ — 1. Razem 8 porównań, wynik: $-1$ (wzorca nie ma). Zauważ rytm 3-1-3-1: koszt pozycji zależy od tego, jak długo tekst „udaje" wzorzec.

⚠️ Uwaga, pułapka

Pusty wzorzec (w = "") to brzeg-filozof: formalnie występuje na każdej pozycji (zero znaków zawsze „pasuje"), więc nasz kod zwróci 0 — wewnętrzna pętla o zerze obrotów zostawia zgadza = True. Czy to dobrze? Wbudowane find odpowiada tak samo, więc jesteśmy w dobrym towarzystwie — ale w specyfikacji warto ten przypadek po prostu wykluczyć ($m \ge 1$), zamiast zdawać się na filozofię. Drugi brzeg: wzorzec dłuższy od tekstu — range(n - m + 1) jest wtedy pusty i funkcja od razu zwraca $-1$; sprawdź, że rozumiesz dlaczego.

🌍 Powiązania

Sprytniejsze algorytmy wyszukiwania (poznasz ideę jednego w 5.6) biją naiwny na tekstach ogromnych albo złośliwych — ale w praktyce codziennej naiwny jest zaskakująco żywotny: dla krótkich wzorców i „normalnych" tekstów bywa najszybszy, bo nie ma żadnych kosztów przygotowania. Zasada inżynierska: najprostsze narzędzie, które wystarcza, jest najlepsze — a mądrzejsze trzymaj na podorędziu, gdy profiler pokaże, że proste nie wystarcza.

🛠️ Teraz Ty

Bez komputera: prześledź znajdz("wowwowo", "wowo") — pozycje, porównania, wynik. Z komputerem: zaimplementuj znajdz_wszystkie(t, w), zwracającą listę wszystkich pozycji wystąpień (nie przerywaj po pierwszym; pomyśl, czy wystąpienia mogą na siebie nachodzić — sprawdź na ("aaaa", "aa")).

📐 Definicje tej lekcji

  • Wyszukiwanie naiwne — przykładanie wzorca na każdej pozycji $0 \dots n-m$ i porównanie znak po znaku z przerwaniem przy niezgodności.
  • Koszt $n \cdot m$ — górna granica porównań; osiągana na tekstach długo „udających" wzorzec.

📌 Najważniejsze w pigułce

  • Pozycje przyłożenia: od 0 do $n - m$ włącznie — pomyłka o jeden gubi wystąpienie na końcu.
  • break przy pierwszej niezgodności; $-1$ jako umowne „nie znaleziono".
  • Najgorszy przypadek $n \cdot m$ zdarza się na tekstach monotonnych; na co dzień naiwny bywa w sam raz.

🎒 Zadania

  1. znajdz("kokos", "kos") — prześledź i podaj wynik oraz łączną liczbę porównań.
Wskazówka i odpowiedź

$i=0$: k✓ o✓ k✗(s… porównujemy t[2]='k' z w[2]='s') — 3. $i=1$: o✗ — 1. $i=2$: k✓ o✓ s✓ — 3, trafione! Wynik: 2, porównań 7. Ciekawostka: „kos" zaczyna się tam, gdzie kończyło się nieudane dopasowanie z $i=0$ — sprytne algorytmy umieją taką wiedzę wykorzystać, naiwny za każdym razem zaczyna od zera.

  1. Zmodyfikuj znajdz tak, by ignorowała wielkość liter (znajdowała „kot" w „Ala ma KOTA"). Gdzie umieścisz normalizację i dlaczego NIE w wewnętrznej pętli?
Wskazówka i odpowiedź

Raz, przed pętlami: t = t.lower(); w = w.lower(). Normalizowanie w wewnętrznej pętli (np. t[i+j].lower()) dawałoby ten sam wynik, ale wykonywało lower miliony razy zamiast raz — to wzorzec ogólny: wyciągaj z pętli wszystko, co niezmienne (spotkasz go przy każdej optymalizacji). Wynik dla przykładu: pozycja 7.

  1. Tekst ma $n = 10^6$ znaków, wzorzec $m = 10$. Oszacuj liczbę porównań: (a) w najgorszym przypadku, (b) w typowym tekście polskim, gdzie niezgodność wypada średnio po ~1,1 znaku. Skomentuj różnicę.
Wskazówka i odpowiedź

(a) $\approx 10^7$ — dziesięć milionów, wciąż ułamek sekundy. (b) $\approx 1{,}1 \cdot 10^6$ — praktycznie jedno przejście po tekście. Naiwny algorytm ma paskudny najgorszy przypadek i świetny przypadek typowy; czy to wystarczy, zależy od zastosowania — edytor tekstu może żyć z (b), system dopasowujący DNA musi projektować pod (a). Analiza kosztu bez pytania „na jakich danych?" jest w połowie pusta.

🔍 Sprawdź, czy umiesz

  • Napisać naiwne wyszukiwanie z pamięci, z poprawnym zakresem pozycji.
  • Prześledzić je na papierze, licząc porównania.
  • Skonstruować dane najgorszego przypadku i wyjaśnić, co je czyni najgorszymi.

Ucz się tej jednostki z asystentem