Algorytm Knutha-Morrisa-Pratta
Sign in to saveAlso known as Knuth–Morris–Pratt string searching algorithm, KMP algorithm, Knuth-Morris-Pratt algorithm
string searching algorithm
Wikidata facts
- Named after
- Vaughan Ronald Pratt
Show 3 more facts
- publication date
- 1970-00-00
- discoverer or inventor
- Vaughan Ronald Pratt
- time of discovery or invention
- 1970-00-00
Sources (1)
via Wikidata · CC0
Article · Polski
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.
Abstract from DBpedia / Wikipedia · CC BY-SA