Wyjaśnij zasadę działania algorytmu wyszukiwania podłańcuchów Knuta-Morrisa-Pratta.
sobes.tech AI
Odpowiedź od AI
Algorytm Knuta-Morrisa-Pratta (KMP) jest przeznaczony do wyszukiwania podłańcucha w łańcuchu w czasie liniowym, unikając powtarzających się porównań znaków.
Główną ideą jest wcześniejsze obliczenie dla podłańcucha tablicy funkcji prefiksowych (lub "tablicy π"), która pokazuje, ile znaków zgadza się z początkiem podłańcucha podczas nieudanej próby porównania. Pozwala to, w przypadku niezgodności, nie wracać do początku w oryginalnym łańcuchu, lecz przesunąć podłańcuch o optymalną liczbę pozycji.
Przykład:
- Tekst: "ABABDABACDABABCABAB"
- Szukany podłańcuch: "ABABCABAB"
Algorytm najpierw tworzy funkcję prefiksową dla podłańcucha, następnie przechodzi przez tekst, porównując znaki. W przypadku niezgodności korzysta z funkcji prefiksowej, aby określić, od którego znaku podłańcucha kontynuować porównanie, nie zaczynając od początku.
To zapewnia złożoność O(n + m), gdzie n to długość tekstu, m to długość podłańcucha, co jest bardziej wydajne niż naiwne wyszukiwanie.