shifts the pattern more than the character-jump heuristic this alternative shift heuristic is based on applying the main idea from the knuth-morris-pratt pattern matching algorithmwhich we discuss next the knuth-morris-pratt algorithm in studying the worst-case performance of the brute-force and bm pattern matching algorithms on specific instances of the problemsuch as that given in example we should notice major inefficiency specificallywe may perform many comparisons while testing potential placement of the pattern against the textyet if we discover pattern character that does not match in the textthen we throw away all the information gained by these comparisons and start over again from scratch with the next incremental placement of the pattern the knuth-morris-pratt (or "kmp"algorithmdiscussed in this sectionavoids this waste of information andin so doingit achieves running time of ( )which is optimal in the worst case that isin the worst case any pattern matching algorithm will have to examine all the characters of the text and all the characters of the pattern at least once the failure function the main idea of the kmp algorithm is to preprocess the pattern string so as to compute failure function that indicates the proper shift of so thatto the largest extent possiblewe can reuse previously performed comparisons specificallythe failure function (jis defined as the length of the longest prefix of that is suffix of [ (note that we did not put [ jherewe also use the convention that ( laterwe will discuss how to compute the failure function efficiently the importance of this failure function is that it "encodesrepeated substrings inside the pattern itself example consider the pattern string "abacabfrom example the knuth-morris-pratt (kmpfailure function (jfor the string is as shown in the following tablethe kmp pattern matching algorithmshown in code fragment incrementally processes the text string comparing it to the pattern string each time there is matchwe increment the current indices on the other handif there is mismatch and we have previously made progress in pthen we consult the failure function to determine the new index in where we need to continue checking against otherwise (there was mismatch and we are at the