On the Expected Sublinearity of the Boyer–Moore Algorithm
Robert Schaback · SIAM Journal on Computing · 1988
This paper analyzes the expected performance of a simplified version $BM'$ of the Boyer–Moore string-matching algorithm. A probabilistic automaton A, which models the expected behavior of $BM'$, is set up under the assumption that both text and pattern are generated by a source which emits independent and uncorrelated symbols with an arbitrary distribution of probabilities. Formal developments lead then to the conclusion that A takes expected sublinear time in a variety of situations. The sublinear behavior can be quantitatively predicted by simple formulae involving the pattern length m and the alphabet’s probabilistic properties. Finally, empirical evidence is provided which is in satisfactory accordance with the theory.