Algorytm KMP (Knutha-Morrisa-Pratta)

Algorytm Knutha-Morrisa-Pratta (KMP) to algorytm wyszukiwania ciągów znaków, który jest używany do wydajnego znajdowania wzorca w dużych tekstach. W przeciwieństwie do naiwnego algorytmu wyszukiwania wzorców, który zaczyna od początku wzorca po każdym niezgodnym dopasowaniu, KMP używa struktury wzorca , aby uniknąć zbędnych porównań. Wstępnie przetwarza ciąg wzorca i tworzy tablicę zwaną tablicą Longest Prefix Suffix (LPS), która wskazuje, ile wzorca można ponownie wykorzystać po niezgodności.

W algorytmie naiwnego wyszukiwania wzorca zaczynamy od każdego indeksu w tekście i porównujemy go z pierwszym znakiem wzorca, jeśli pasują, przechodzimy do następnego znaku zarówno w tekście, jak i we wzorcu. Jeśli występuje niezgodność, rozpoczynamy ten sam proces dla następnego indeksu tekstu.

Przykład:

• Dane wejściowe: txt= „aabaacaadaabaaba”, pattern = „aaba”
• Wynik: [0, 9, 12]
  • Wzorzec „aaba” występuje w ciągu wejściowym txt trzy razy: zaczynając od indeksów 0, 9 oraz 12

Implementacja algorytmu KMP

Inicjujemy dwa wskaźniki, jeden dla ciągu tekstowego i drugi dla wzorca. Gdy znaki przy obu wskaźnikach są zgodne, zwiększamy oba wskaźniki i kontynuujemy porównanie. Jeśli nie są zgodne, resetujemy wskaźnik wzorca do ostatniej wartości z tablicy LPS, ponieważ ta część wzorca została już dopasowana do ciągu tekstowego. Podobnie, jeśli przeszliśmy cały ciąg wzorca, dodajemy indeks początkowy wystąpienia wzorca w tekście do wyniku i kontynuujemy wyszukiwanie od wartości LPS ostatniego elementu wzorca.

def longest_prefix_suffix(txt):
    n = len(txt)
    lps = [0] * n
    
    # len przechowuje najdłuższy prefix, któryc jest również sufixem dla poprzedniego indexu
    length = 0
    # lps[0] jest zawsze 0
    lps[0] = 0
    i = 1
    while i < n:
        # jeśli znaki się zgadzają to zwiększ długość lps
        if txt[i] == txt[length]:
            length += 1
            lps[i] = length
            i += 1
        # w przypadku gdy się nie zgadzają
        else:
            if length != 0:
                # Zaaktualizuj długość poprzedniego indexu lps, abu uniknąć niepotrzebnych porównań
                length = lps[length - 1]
            else:
              
                # jeśli nie znaleziono psaującego predixu, ustaw wartość lps[i] = 0
                lps[i] = 0
                i += 1
    return lps

def knp_search(txt, pattern):
    n = len(txt)
    m = len(pattern)

    res = []
    lps = longest_prefix_suffix(pattern)

    # Wskaźniki do przechodzenia przez tekst oraz wzorzec
    i = 0
    j = 0

    while i < n:
        # Jeśli znaki się zgadzają, zwiększ oba wskaźniki
        if txt[i] == pattern[j]:
            i += 1
            j += 1

            # Jeśli cały wzorzec jest dopasowany, zapisz indeks początkowy w wyniku
            if j == m:
                res.append(i - j)
                
                # Użyj LPS poprzedniego indeksu, aby pominąć niepotrzebne porównania
                j = lps[j - 1]
        
        # Jeśli znaki są inne
        else:
            # Użyj LPS poprzedniego indeksu, aby pominąć niepotrzebne porównania
            if j != 0:
                j = lps[j - 1]
            else:
                i += 1
    return res 

txt = "aabaacaadaabaaba"
pat = "aaba"

index_arr = knp_search(txt, pat)
print(index_arr)

• Złożoność czasowa: O(n + m), gdzie n to długość tekstu, a m to długość wzorca. Dzieje się tak, ponieważ utworzenie tablicy LPS (Longest Prefix Suffix) zajmuje O(m) czasu, a przeszukanie tekstu zajmuje O(n) czasu.
• Złożoność pamięciowa: O(m), ponieważ musimy przechowywać tablicę LPS o rozmiarze m.