Zadanie

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)

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 ich długości. O(mn)

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 algorytmów wyszukiwania tekstu. m — długość wzorca, n — długość tekstu, k — rozmiar alfabetu.
AlgorytmPre-processingWyszukiwanie
Algorytm naiwnyO(1)O(mn)
Knuth–Morris–Pratt O(m)O(n)
Boyer–Moore O(m+k)best \Omega(n/m), worst O(nm)