the knuth-morris-pratt algorithm in examining the worst-case performances of the brute-force and boyer-moore pattern-matching algorithms on specific instances of the problemsuch as that given in example we should notice major inefficiency for certain alignment of the patternif we find several matching characters but then detect mismatchwe ignore all the information gained by the successful comparisons after restarting 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 asymptotically optimal 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 main idea of the kmp algorithm is to precompute self-overlaps between portions of the pattern so that when mismatch occurs at one locationwe immediately know the maximum amount to shift the pattern before continuing the search motivating example is shown in figure textpatterna figure motivating example for the knuth-morris-pratt algorithm if mismatch occurs at the indicated locationthe pattern could be shifted to the second alignmentwithout explicit need to recheck the partial match with the prefix ama if the mismatched character is not an lthen the next potential alignment of the pattern can take advantage of the common the failure function to implement the kmp algorithmwe will precompute failure functionf that indicates the proper shift of upon failed comparison specificallythe failure function (kis defined as the length of the longest prefix of that is suffix of [ : + (note that we did not include [ heresince we will shift at least one unitintuitivelyif we find mismatch upon character [ + ]the function (ktells us how many of the immediately preceding characters can be reused to restart the pattern example describes the value of the failure function for the example pattern from figure