Algorytm Knuth-Morris-Pratt (KMP)

1. Problem z algorytmem naiwnym

Algorytm naiwny marnuje informacje z poprzednich porównań:

Text:    AAAAAAB
Pattern: AAAB

Pozycja 0: AAAA vs AAAB
           ✓✓✓✗

Pozycja 1: AAAA vs AAAB  ← Znów porównujemy te same A!
           ✓✓✓✗

Problem: Nie wykorzystujemy faktu, że już znamy pierwsze 3 A!

KMP rozwiązuje ten problem!

2. Idea algorytmu KMP

Knuth-Morris-Pratt (1977) wykorzystuje preprocessing wzorca do uniknięcia zbędnych porównań.

2.1. Kluczowa obserwacja:

Gdy znajdziemy niezgodność, możemy pominąć niektóre pozycje, bo już wiemy, co jest w tekście!

Text:    ABABCABABA
Pattern: ABABD
         ✓✓✓✓✗ (niezgodność na D)

Wiemy, że text[0:4] = "ABAB" (dopasowane)

Zamiast przesuwać pattern o 1:
  ABABCABABA
   ABABD  ← Bez sensu! "B" != "A"

Przesuwamy inteligentnie:
  ABABCABABA
     ABABD  ← Kontynuuj od "AB"

KMP nigdy nie cofa się w tekście! Skanuje tekst tylko raz. ✅

3. Tablica LPS (Longest Proper Prefix which is also Suffix)

3.1. Czym jest LPS?

LPS[i] = długość najdłuższego właściwego prefiksu, który jest także sufiksem dla pattern[0:i+1].

Właściwy prefiks = prefiks krótszy niż cały string.

3.2. Przykład:

Pattern: "ABABD"

i=0: "A"
  Prefiksy: "" (pusty)
  Sufiksy: "" (pusty)
  LPS[0] = 0

i=1: "AB"
  Prefiksy: "", "A"
  Sufiksy: "", "B"
  Wspólne: ""
  LPS[1] = 0

i=2: "ABA"
  Prefiksy: "", "A", "AB"
  Sufiksy: "", "A", "BA"
  Wspólne: "A"
  LPS[2] = 1

i=3: "ABAB"
  Prefiksy: "", "A", "AB", "ABA"
  Sufiksy: "", "B", "AB", "BAB"
  Wspólne: "AB"
  LPS[3] = 2

i=4: "ABABD"
  Prefiksy: "", "A", "AB", "ABA", "ABAB"
  Sufiksy: "", "D", "BD", "ABD", "BABD"
  Wspólne: ""
  LPS[4] = 0

LPS = [0, 0, 1, 2, 0]

3.3. Zastosowanie LPS:

Gdy znajdziemy niezgodność na pattern[j], przeskakujemy do pattern[LPS[j-1]] zamiast zaczynać od początku!

4. Budowanie tablicy LPS

4.1. Algorytm:

Złożoność: O(m) – liniowa! ✅

4.2. Wizualizacja budowania LPS:

Pattern: "ABABD"

i=0: lps[0] = 0 (zawsze)

i=1: pattern[1]='B' vs pattern[0]='A'
     B != A → lps[1] = 0

i=2: pattern[2]='A' vs pattern[0]='A'
     A == A → length=1, lps[2] = 1

i=3: pattern[3]='B' vs pattern[1]='B'
     B == B → length=2, lps[3] = 2

i=4: pattern[4]='D' vs pattern[2]='A'
     D != A → cofnij: length = lps[1] = 0
     D != pattern[0]='A' → lps[4] = 0

LPS = [0, 0, 1, 2, 0]

5. Wyszukiwanie KMP

5.1. Implementacja:

Złożoność: - Preprocessing: O(m) - Wyszukiwanie: O(n) - Razem: O(n + m) ✅

6. Wizualizacja działania KMP

Text:    ABABCABABA
Pattern: ABABD
LPS:     [0, 0, 1, 2, 0]

i=0, j=0: text[0]='A' == pattern[0]='A' ✓
i=1, j=1: text[1]='B' == pattern[1]='B' ✓
i=2, j=2: text[2]='A' == pattern[2]='A' ✓
i=3, j=3: text[3]='B' == pattern[3]='B' ✓
i=4, j=4: text[4]='C' != pattern[4]='D' ✗

  Niezgodność! j=4, więc:
  j = lps[j-1] = lps[3] = 2

i=4, j=2: text[4]='C' != pattern[2]='A' ✗

  Niezgodność! j=2, więc:
  j = lps[j-1] = lps[1] = 0

i=4, j=0: text[4]='C' != pattern[0]='A' ✗
  j=0, więc i++

i=5, j=0: text[5]='A' == pattern[0]='A' ✓
i=6, j=1: text[6]='B' == pattern[1]='B' ✓
i=7, j=2: text[7]='A' == pattern[2]='A' ✓
i=8, j=3: text[8]='B' == pattern[3]='B' ✓
i=9, j=4: text[9]='A' != pattern[4]='D' ✗

  Niezgodność! j=4, więc:
  j = lps[j-1] = lps[3] = 2

i=9, j=2: text[9]='A' == pattern[2]='A' ✓
i=10, j=3: Koniec tekstu

Nie znaleziono dopasowania dla "ABABD"

7. Debug version z wizualizacją

8. Porównanie: KMP vs Naiwny

8.1. Najgorszy przypadek:

8.2. Liczba porównań:

Text:    AAAAAAB (7 znaków)
Pattern: AAAB (4 znaki)

Algorytm naiwny:
- Pozycja 0: AAAA vs AAAB → 4 porównania
- Pozycja 1: AAAA vs AAAB → 4 porównania
- Pozycja 2: AAAA vs AAAB → 4 porównania
- Pozycja 3: AAAB vs AAAB → 4 porównania ✓
Razem: 16 porównań

KMP:
- Preprocessing: O(m) = 4 operacje
- Wyszukiwanie: każdy znak tekstu sprawdzany raz = 7 porównań
Razem: ~11 operacji (znacznie mniej!)

9. Zastosowania KMP

9.1. Znajdowanie wszystkich wystąpień:

9.2. Sprawdzanie, czy pattern występuje:

9.3. Znajdowanie pierwszego wystąpienia:

10. Modyfikacje algorytmu KMP

10.1. Case-insensitive KMP:

10.2. Liczenie wystąpień:

11. Powtarzające się wzorce w tekście

12. Benchmark KMP vs inne algorytmy

13. Podsumowanie

Algorytm Knuth-Morris-Pratt (KMP):

Efektywny algorytm wyszukiwania wzorca
Preprocessing wzorca → tablica LPS
Nigdy nie cofa się w tekście ✅
Gwarantowana złożoność O(n + m)

Złożoność:

Operacja	Złożoność	Uwagi
Preprocessing	O(m)	Budowanie tablicy LPS
Wyszukiwanie	O(n)	Jeden przebieg tekstu
Razem	O(n + m) ✅	Liniowa! Najgorszy = średni
Pamięć	O(m)	Tablica LPS

Tablica LPS:

LPS[i] = długość najdłuższego właściwego prefiksu pattern[0:i+1],
         który jest także sufiksem

Przykład: "ABABD" → LPS = [0, 0, 1, 2, 0]

Implementacja budowania LPS:

Implementacja KMP:

Zalety: - ✅ O(n + m) gwarantowane – nawet najgorszy przypadek! - ✅ Nigdy nie cofa się w tekście (jeden przebieg) - ✅ Efektywny dla długich wzorców - ✅ Efektywny dla powtarzających się znaków - ✅ Znajduje wszystkie wystąpienia (overlapping)

Wady: - ❌ Wymaga preprocessingu (tablica LPS) - ❌ O(m) dodatkowej pamięci - ❌ Bardziej skomplikowany niż naiwny - ❌ W praktyce często wolniejszy od Boyer-Moore

Porównanie:

Algorytm	Najgorszy	Preprocessing	Pamięć	Prostota
Naiwny	O(n×m) ❌	Brak	O(1) ✅	Bardzo prosta
KMP	O(n+m) ✅	O(m)	O(m)	Średnia
Boyer-Moore	O(n×m)	O(m + σ)	O(m + σ)	Złożona
Rabin-Karp	O(n×m)	O(m)	O(1)	Średnia

Kiedy używać KMP:

✅ Długie wzorce (m > 100) ✅ Najgorszy przypadek krytyczny (AAAA...B) ✅ Gwarancja O(n + m) wymagana ✅ Streaming – przetwarzanie tekstu w locie ✅ Edukacja – elegancki algorytm do nauki

❌ Krótkie wzorce → naiwny wystarczy ❌ Losowe dane → Boyer-Moore szybszy ❌ Wiele wzorców → Aho-Corasick ❌ Proste zadania → Python builtin

Kluczowa obserwacja:

KMP wykorzystuje informację z poprzednich porównań!

Text:    ABABCABABA
Pattern: ABABD
         ✓✓✓✓✗

Wiemy, że dopasowane "ABAB" ma prefiks "AB" == sufiks "AB"
Więc możemy przeskoczyć:

  ABABCABABA
     AB...  ← Kontynuuj od "AB", nie od początku!

Zastosowania w praktyce:

Kompilatory (lexical analysis)
Wyszukiwarki tekstu (grep, find)
Bioinformatyka (DNA sequences)
Intrusion detection systems
Data compression algorithms

Co dalej warto poznać:

Boyer-Moore – szybszy w praktyce (skanuje od końca)
Rabin-Karp – hashing, dobry dla wielu wzorców
Aho-Corasick – wiele wzorców jednocześnie (KMP++)
Z-algorithm – wszystkie prefiksy w O(n)
Suffix Array/Tree – zaawansowane struktury