Algorytm Knutha-Morrisa-Pratta

Algorytm Knutha-Morrisa-Pratta – algorytm wyszukiwania wzorca w tekście. Algorytm wykorzystuje fakt, że w przypadku wystąpienia niezgodności ze wzorcem, sam wzorzec zawiera w sobie informację pozwalającą określić, gdzie powinna się zacząć kolejna próba dopasowania, pomijając ponowne porównywanie już dopasowanych znaków. Dzięki temu właściwy algorytm działa w okresie liniowym względem długości przeszukiwanego tekstu i wzorca. Ma to znaczenie dla dużych wzorców. Algorytm został wynaleziony przez Donalda Knutha i Vaughana Pratta i niezależnie przez w 1977, ale wszyscy trzej opublikowali go wspólnie.