On the Average-Case Running Time of the Boyer-Moore Algorithm

The Boyer-Moore algorithm (BM) is a fast, compact algorithm for finding all occurrences of a pattern string in a text string. Previous papers have addressed the worst-case running time of BM, which occurs rarely in practice. In this paper, we derive an approximation to Φ (BM) the average number of character probes made by BM. Let M = pattern length, N = text string length, α = the alphabet size, q = 1 /α and q= I — q. By modeling BM as a probabilistic finite automaton, we show that Φ(BM) h when M \u3c α and that Φ(BM ) N q(l + g V ) when M \u3e α. An immediate consequence is that Φ(BM) is O(N/ log α M) as M -\u3e \infty The above formulas match well with measured data