Knuth-Morris-Pratt algorithmIdea After a shift of the pattern, the naive algorithm has forgotten all information about previously matched symbols. So it is possible that it re-compares a text symbol with different pattern symbols again and again. This leads to its worst case complexity of Θ(nm) (n: length of the text, m: length of the pattern). The algorithm of Knuth, Morris and Pratt [KMP 77] makes use of the information ga
