Zadanie, przed którym stajemy: znajdź wzorzec w podanym ciągu znaków
Mamy tekst A o długości N, zawierający K różnych znaków. Mamy również szukany wzorzec B o długości M znaków, M<N. Znajdź pozycję, na której w tekście A znajduje się wzorzec B.
Przykład:
szukamy wzorca “NSAENFCVSBGIJTU” w zadanym tekście: “AAAAABBBCCCSVMSOVLNSAENFCVSBGIJTUYHFDYDRRRRRHNFJMGTDR”
Algorytm naiwny
Porównujemy wzorzec z tekstem i gdy natrafimy na pierwszą różnicę, wówczas przesuwamy wzorzec o jedną pozycję. Taki naiwny algorytm możemy zaimplementować następująco:
text = "AAAAABBBCCCSVMSOVLNSAENFCVSBGIJTUYHFDYDRRRRRHNFJMGTDR"
pattern = "NSAENFCVSBGIJTU"
def fing_pattern_naive_algorithm(text, pattern):
text_len = len(text)
pattern_len = len(pattern)
for i in range(text_len - pattern_len):
pattern_match = True
for j in range(len(pattern)):
if text[i + j] != pattern[j]:
pattern_match = False
break
if pattern_match:
return i
return -1
result = fing_pattern_naive_algorithm(text, pattern)Uzyskujemy złożoność:
Nie alokujemy pamięci zależnej od długości danych wejściowych, więc mamy stałą złożoność pamięciową. Dwie zagnieżdżone pętle iterujące po tekście i wzorcu dają nam złożoność obliczeniową równą iloczynowi długości argumentów.
Porównanie algorytmów
Wszystkie algorytmy poza naiwnym składają się z dwóch faz: przetworzenia tekstu i wyszukiwania wzorca. Dlatego złożoność czasowa została przedstawiona osobno dla każdego z etapów przetwarzania.
| Złożoność obliczeniowa pre-procesing | Złożoność obliczeniowa wyszukiwania | |
|---|---|---|
| Algorytm naiwny | ||
| Knuth Morris Pratt | ||
| Boyer Moore |
| m | długość wzorca |
| n | długość tekstu |
| k | rozmiar alfabetu |