The Boyer-Moore algorithm


Summary
The boyer-moore vocabulary implements a Boyer-Moore string search algorithm with so-called 'strong good suffix shift rule'. Since algorithm is alphabet-independent it is applicable to searching in any collection that implements Sequence protocol.

Complexity
Let n and m be lengths of the sequences being searched in and for respectively. Then searching runs in O(n) time in its worst case using additional O(m) space. The preprocessing phase runs in O(m) time.