Algorytm Knutha-Morrisa-Pratta – algorytm wyszukiwania wzorca w tekście.
Przykład działania Rozważmy przykład działania algorytmu KMP, w którym szukamy wzorca ABCDABD w tekście ABC ABCDAB ABCDABCDABDE.
Tablica niepowodzeń (prefix table) Pierwszym krokiem algorytmu jest wygenerowanie tzw. tablicy niepowodzeń (ang. failure function), która dla każdego znaku we wzorcu określa najdłuższy właściwy prefiks będący zarazem sufiksem.
Dla wzorca ABCDABD tablica wygląda następująco:
Indeks (i) 0 1 2 3 4 5 6 Znak A B C D A B D Prefix table 0 0 0 0 1 2 0
Działanie na tekście Podczas przeszukiwania tekstu, gdy napotkamy niezgodność znaków, algorytm wykorzystuje tablicę niepowodzeń do przesunięcia wzorca bez cofania się w tekście, co pozwala uniknąć zbędnych porównań.
Dzięki temu algorytm wykonuje wyszukiwanie w czasie O(n + m), gdzie n to długość tekstu, a m – długość wzorca.
Pseudokod Poniżej przedstawiono uproszczony pseudokod algorytmu:
function KMP(text, pattern): lps = compute_prefix_function(pattern) i = 0 # indeks tekstu j = 0 # indeks wzorca
while i < len(text): if pattern[j] == text[i]: i += 1 j += 1 if j == len(pattern): print("Znaleziono wzorzec na pozycji", i - j) j = lps[j - 1] elif i < len(text) and pattern[j] != text[i]: if j != 0: j = lps[j - 1] else: i += 1