Tight Bounds on the Complexity of the Boyer–Moore String Matching Algorithm

Abstract

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 $\frac{n}{m} \to \infty $ and $m \to \infty $. While the upper bound is somewhat involved, its main elements provide a simple proof of a $4n$ upper bound for the same algorithm.