Summary

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

Complexity

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

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

Complexity

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