Let A be a nite alphabet, jAj =: n, and suppose strings

Abstract. This paper analyzes the expected performance of a simplied version BM 0 of the Boyer{Moore string matching algorithm. A probabilistic automaton A is set up which models the expected behavior of BM 0 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