Knuth–Morris–Pratt algorithm

views updated

Knuth–Morris–Pratt algorithm (KMP algorithm) A method of finding patterns, developed by D. E. Knuth, J. H. Morris and V. R. Pratt. It can be used for example to find a certain pattern within a list of letters: the first letter in the list is stored in an array and subsequent letters added until the pattern is no longer followed or is completed; on failure the next letter is chosen and so on.