SummaryThe
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.
ComplexityLet
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.