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 performance excluding the computation of the failure functionthe running time of the kmp algorithm is clearly proportional to the number of iterations of the while loop for the sake of the analysislet us define intuitivelyk is the total amount by which the pattern has been shifted with respect to the text note that throughout the execution of the algorithmwe have < one of the following three cases occurs at each iteration of the loop if [ip[ ]then increases by and does not changesince also increases by if [ip[jand then does not change and increases by at least since in this case changes from to ( )which is an addition of ( )which is positive because ( if [ip[jand then increases by and increases by since does not change 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 pattern matching algorithm is at most achieving this boundof courseassumes that we have already computed the failure function for