Wyszukiwanie wzorca - algorytm naiwny

1. Problem wyszukiwania wzorca

Pattern matching (wyszukiwanie wzorca) to fundamentalny problem polegający na znalezieniu wszystkich wystąpień wzorca (pattern) w tekście (text).

1.1. Definicja problemu:

Dane:
- text = "ABABCABABA"
- pattern = "ABA"

Zadanie: Znajdź wszystkie indeksy, gdzie pattern występuje w text

Wynik: [0, 5, 7]
         ↓     ↓  ↓
text = "ABA BCABA BA"
        ^^^   ^^^ ^^^

1.2. Zastosowania:

  • Edytory tekstu – Ctrl+F, Find & Replace
  • Wyszukiwarki – Google, indeksowanie stron
  • Bioinformatyka – szukanie sekwencji DNA
  • Wykrywanie wirusów – sygnatury malware
  • Kompilatory – parsowanie kodu
  • Plagiat detection – porównywanie dokumentów

2. Algorytm naiwny - idea

Najprostsze podejście:

  1. Porównuj wzorzec z każdą możliwą pozycją w tekście
  2. Dla każdej pozycji sprawdź znak po znaku
  3. Jeśli wszystkie znaki pasują → znaleziono!

2.1. Wizualizacja:

text    = "ABABCABABA"
pattern = "ABA"

Pozycja 0:
ABA BCABABA
ABA ✓✓✓ → Znaleziono!

Pozycja 1:
A BAB CABABA
  ABA ✗ (B != A)

Pozycja 2:
AB ABC ABABA
   ABA ✗ (B != A)

Pozycja 3:
ABA BCA BABA
    ABA ✗ (B != A)

...kontynuuj...

3. Implementacja podstawowa

Złożoność: - Najgorszy przypadek: O(n × m) - Pamięć: O(1) (nie licząc wyniku)

4. Implementacja z debugiem

Wynik:

Text:    ABABCABABA
Pattern: ABA

Pozycja 0:
  Text[0:3] = "ABA"
  ✓ ZNALEZIONO!

Pozycja 1:
  Text[1:4] = "BAB"
  ✗ text[1]='B' != pattern[0]='A'

Pozycja 2:
  Text[2:5] = "ABC"
  ✓ ZNALEZIONO!
...

5. Optymalizacja - wczesne przerwanie

Zaleta: Przerywa od razu po pierwszej niezgodności.

6. Analiza złożoności

6.1. Najgorszy przypadek - O(n × m):

Złożoność: O((n - m + 1) × m) = O(n × m)

6.2. Najlepszy przypadek - O(n):

Złożoność: O(n - m + 1) ≈ O(n)

6.3. Średni przypadek:

Dla losowych danych: O(n) – większość pozycji odrzucana szybko.

7. Warianty algorytmu naiwnego

7.1. Case-insensitive wyszukiwanie:

7.2. Wyszukiwanie z wildcard:

7.3. Zliczanie wystąpień:

7.4. Tylko pierwsze wystąpienie:

8. Porównanie z wbudowanymi funkcjami

8.1. Python str.find():

8.2. Python in operator:

9. Benchmark

10. Problemy praktyczne

10.1. Najdłuższy powtarzający się substring:

Złożoność: O(n³) – bardzo wolne!

10.2. Znajdowanie wszystkich unikalnych substringów:

11. Kiedy algorytm naiwny jest wystarczający?

✅ Używaj algorytmu naiwnego gdy:

  1. Krótki wzorzec (m < 10)
  2. Mały tekst (n < 1000)
  3. Jednorazowe wyszukiwanie
  4. Losowe dane (średnio O(n))

❌ Użyj zaawansowanych algorytmów gdy:

  1. Długi wzorzec (m > 100)
  2. Duży tekst (n > 10000)
  3. Wiele wyszukiwań (ten sam tekst)
  4. Najgorszy przypadek (text="AAA...", pattern="AAA...")

12. Wady algorytmu naiwnego

13. Podsumowanie

Algorytm naiwny:

  • Najprostszy algorytm wyszukiwania wzorca
  • Sprawdza każdą możliwą pozycję w tekście
  • Porównuje znak po znaku

Złożoność:

Przypadek Złożoność czasowa Przykład
Najgorszy O(n × m) ❌ text="AAA...", pattern="AAA"
Najlepszy O(n) ✅ Brak dopasowań
Średni O(n) Losowe dane
Pamięć O(1) Brak dodatkowej pamięci

Implementacja podstawowa:

Zalety: - ✅ Bardzo prosty do implementacji - ✅ Nie wymaga preprocessingu - ✅ O(1) pamięci - ✅ Dobry dla małych danych - ✅ Dobry dla losowych danych (średnio O(n))

Wady: - ❌ O(n × m) w najgorszym przypadku - ❌ Nie wykorzystuje informacji z poprzednich porównań - ❌ Wolny dla długich wzorców - ❌ Nieefektywny dla powtarzających się znaków

Kiedy używać:

✅ Małe dane (n < 1000, m < 10) ✅ Jednorazowe wyszukiwanie ✅ Prototypowanie – szybka implementacja ✅ Losowe dane – średnio O(n)

❌ Duże dane → użyj KMP, Boyer-Moore ❌ Długi wzorzec → użyj Rabin-Karp ❌ Wiele wzorców → użyj Aho-Corasick ❌ Fuzzy matching → użyj edit distance

Porównanie z Python builtin:

Kluczowa obserwacja:

Algorytm naiwny NIE zapamiętuje porównań:

Text:    AAAAAAB
Pattern: AAAB

Pozycja 0: AAAA vs AAAB → 4 porównania ✗
Pozycja 1: AAAA vs AAAB → 4 porównania ✗ (znów te same A!)
Pozycja 2: AAAA vs AAAB → 4 porównania ✗
Pozycja 3: AAAB vs AAAB → 4 porównania ✓

Razem: 16 porównań dla 7 znaków!

Zaawansowane algorytmy (KMP, BM) wykorzystują te informacje! ✅

Co dalej warto poznać:

  • Knuth-Morris-Pratt (KMP) – O(n + m), preprocessing wzorca
  • Boyer-Moore – szybszy w praktyce, skanuje od końca
  • Rabin-Karp – hashing, dobry dla wielu wzorców
  • Aho-Corasick – wiele wzorców jednocześnie
  • Suffix Array/Tree – zaawansowane struktury danych
Wróć do spisu lekcji