A new proof of the linearity of the Boyer-Moore string searching algorithm

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.