R. Cole

SIAM Journal on Computing, 5(1994), 1075-1091.

The problem of finding all occurrences of a pattern of length m in a text of length n is considered. It is shown that the Boyer-Moore string matching algorithm performs roughly 3n comparisons and that this bound is tight up to O(n/m); more precisely, an upper bound of 3n-3(n-m+1)/(m+2) comparisons is shown, as is a lower bound of 3n(1-o(1)) comparisons, as n/m and m tend to infinity. While the upper bound is somewhat involved, its main elements provide a quite simple proof of a 4n upper bound for the same algorithm.