Knuth-Morris-Pratt

From Algorithmist
Jump to navigation Jump to search

The Knuth-Morris-Pratt (KMP) algorithm is an algorithm for finding a pattern in a string.

The algorithm was conceived in 1974 by Donald Knuth and Vaughan Pratt, and independently by James H. Morris. The three published it jointly in 1977.

Time Complexity[edit]

The algorithm's time complexity is if and are the lengths of the pattern and the text. This is better than the trivial solution.

See Also[edit]

  • Boyer-Moore which has a time complexity of

External Links[edit]

This is a stub or unfinished. Contribute by editing me.