On the expected sublinearity of the Boyer-Moore algorithm

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