Wyszukiwanie maksymalnego prefikso-sufiksu

Zadaniem wyszukiwania maksymalnego prefikso-sufiksu lub najdłuższego prefikso-sufiksu (ang. Longest Prefix Suffix) jest znalezienie ciągu tekstowego, który jest jest zarówno prefiksem jak i sufiksem przeszukiwanego tekstu.

Poniżej przedstawione zostały dwa podejścia rozwiązania tego problemu.

Algorytm naiwny wyszukiwania maksymalnego prefikso-sufiksu

Najprostszym podejściem jest porównanie każdego właściwego prefiksu z sufiksem. Minimalna długość właściwego prefiksu wynosi zero, a maksymalna długość to length – 1. Tak więc iterujemy po każdej długości i sprawdzamy, czy właściwy prefiks tego rozmiaru pasuje do sufiksu tego samego rozmiaru. Jeśli pasują, odpowiednio aktualizujemy wynik.

Złożoność czasowa algorytmu to O(n²), a pamięciowa to O(1).

# defnicja funkcji maksymalnego prefikso-sufiksu z użyciem metody naiwnej
def longest_prefix_suffix(s):
    res = 0
    n = len(s)
    
    # iteracja po wszystkich możliwych długościach ciągu tekstowego
    for length in range(1, n):
        
        # Index początkowy szukanego prefixu
        i = 0
        
        # Index początkowy szukanego sufixu
        j = n - length
        
        flag = True
        
        # Porównanie prefixu oraz sufixu
        for k in range(length):
            if s[i + k] != s[j + k]:
                flag = False
                break
        
        # Aktualizacja wyniku, jeśli ciągi tekstowe pasują
        if flag:
            res = length
    
    return res

s = "ababab"
print(longest_prefix_suffix(s))

Użycie algorytmu KMP dla wyszukiwania maksymalnego prefikso-sufiksu

Metoda ta polega na wykorzystaniu etapu wstępnego przetwarzania algorytmu KMP (Knutha-Morrisa-Pratta) do wyszukiwania wzorców. W tym etapie budujemy tablicę lps, w której każdy indeks i przechowuje długość najdłuższego właściwego prefiksu podciągu str[0…i], który jest również sufiksem tego samego podciągu. Tak więc ostatni indeks tablicy lps będzie przechowywał długość najdłuższego prefiksu, który jest również sufiksem całego ciągu.

Złożoność czasowa algorytmu to O(n), a pamięciowa to O(n).

# defnicja funkcji tworzenia maksymalnego prefikso-sufiksu
def longest_prefix_suffix(s):
    n = len(s)
    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 s[i] == s[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
    
    # Ostatni element tablicy lps przechowuje długość najdłuższego prefixu, który jest również sufixem przeszukiwanego ciągu tekstowego
    return lps[n - 1]

s = "ababab"
print(longest_prefix_suffix(s))