A New Proof of the Linearity of the Boyer-Moore String Searching Algorithm
Leo J. Guibas, Andrew M. Odlyzko · SIAM Journal on Computing · 1980
The Boyer-Moore algorithm searches for all occurrences of a specified string, the pattern, in another string, the text. We study the combinatorial structure of periodic strings and use these results to derive a new proof of the linearity of the Boyer-Moore algorithm in the worst case. Our proof reduces the previously best known bound of $7n$ to $4n$, where n is the length of the text.