The Knuth-Morris-Pratt algorithm (KMP) is an algorithm for motif finding first published in 1977. It improved on the naive "sliding window" approach to finding a motif by introducing the failure array. For details of the algorithm, please consult the Wikipedia page for KMP provided below.