# Knuth-Morris-Pratt

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. |