the correctness of the boyer-moore pattern-matching algorithm follows from the fact that each time the method makes shiftit is guaranteed not to "skipover any possible matches for last(cis the location of the last occurrence of in in figure we illustrate the execution of the boyer-moore pattern-matching algorithm on an input string similar to example texta last(ca - patterna figure an illustration of the boyer-moore pattern-matching algorithmincluding summary of the last(cfunction the algorithm performs character comparisonswhich are indicated with numerical labels performance if using traditional lookup tablethe worst-case running time of the boyer-moore algorithm is (nm | |namelythe computation of the last function takes time ( | |)and the actual search for the pattern takes (nmtime in the worst casethe same as the brute-force algorithm (with hash tablethe dependence on |sis removed an example of text-pattern pair that achieves the worst case is aaaaaaa -  aa the worst-case performancehoweveris unlikely to be achieved for english textforin that casethe boyer-moore algorithm is often able to skip large portions of text experimental evidence on english text shows that the average number of comparisons done per character is for five-character pattern string we have actually presented simplified version of the boyer-moore algorithm the original algorithm achieves running time (nm | |by using an alternative shift heuristic to the partially matched text stringwhenever it 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