Exact Matching: A Deeper Look at Classical Methods
3.1. A Boyer–Moore variant with a “simple” linear time bound
Apostolico and Giancarlo  suggested a variant of the Boyer–Moore algorithm that allows a fairly simple proof of linear worst-case running time. With this variant, no character of T will ever be compared after it is first matched with any character of P. It is then immediate that the number of comparisons is at most 2m: Every comparison is either a match or a mismatch; there can only be m mismatches since each one results in a nonzero shift of P; and there can only be m matches since no character of T is compared again after it ...