thusat each iteration of the loopeither or increases by at least (possibly both)hencethe total number of iterations of the while loop in the kmp patternmatching algorithm is at most achieving this boundof courseassumes that we have already computed the failure function for the algorithm for computing the failure function runs in (mtime its analysis is analogous to that of the main kmp algorithmyet with pattern of length compared to itself thuswe haveproposition the knuth-morris-pratt algorithm performs pattern matching on text string of length and pattern string of length in ( mtime the correctness of this algorithm follows from the definition of the failure function any comparisons that are skipped are actually unnecessaryfor the failure function guarantees that all the ignored comparisons are redundant--they would involve comparing the same matching characters over again in figure we illustrate the execution of the kmp pattern-matching algorithm on the same input strings as in example note the use of the failure function to avoid redoing one of the comparisons between character of the pattern and character of the text also note that the algorithm performs fewer overall comparisons than the brute-force algorithm run on the same strings (figure the failure function [kf (ktextpatterna no comparison performed figure an illustration of the kmp pattern-matching algorithm the primary algorithm performs character comparisonswhich are indicated with numerical labels (additional comparisons would be performed during the computation of the failure function