Sposób działania algorytmu oparty jest na odnajdywaniu różnic pomiędzy wzorcem a tekstem, gdzie wzorzec wskazuje dalsze różnice. Kluczowym elementem algorytmu jest wstępne przetworzenie wzorca w celu obliczenia tzw. tablicy przesunięć, która pozwala uniknąć niepotrzebnych porównań, co znacząco przyspiesza proces wyszukiwania.
Złożoność czasowa algorytmu Knutha-Morrisa-Pratta wynosi O(n + m), gdzie n to długość przeszukiwanego tekstu, a m to długość wzorca. Przekłada się to na wydajne wyszukiwanie, nawet w długich tekstach, a także na możliwość zastosowania algorytmu w systemach wymagających szybkiego przetwarzania danych, takich jak wyszukiwarki internetowe, systemy baz danych czy bioinformatyka.
Algorytm został wynaleziony w 1977 roku przez Donalda Knutha i Vaughana Pratta oraz niezależnie przez . Opublikowany został w jednej pracy, której autorami była cała trójka. Był to pierwszy algorytm wyszukiwania wzorca w tekście o liniowej złożoności czasowej.
Algorytm KMP Przykład działania W tym artykule przyjęto jako konwencję indeksowanie tablic służących do przechowywania łańcuchów znaków od zera. Oznacza to, że pierwszy element tablicy ma indeks 0, drugi ma indeks 1, trzeci – indeks 2 itd.