Boyer-Moore
Boyer-Moore compares from the right-hand end like Horspool, but keeps two tables. The bad-character rule asks where the mismatching text character last appears in the pattern. The good-suffix rule asks where else in the pattern the part that already matched could line up. Both give a safe distance, and the algorithm moves by the larger.
How far it jumps
Ask two rules how far is safe, and take the larger answer.
When it is the right choice
It is the classical answer for searching a long text with a long pattern, and the one the good implementations are descended from. The extra table costs O(m) to build and its arithmetic is fiddly, which is exactly why Horspool — bad-character only — is more common in practice. Where it pays is text that partially matches often: the good-suffix rule uses what matched, which the bad-character rule throws away.
How it works
- Build the bad-character table: the last position at which each character appears in the pattern.
- Build the good-suffix table, by finding for each suffix of the pattern where else that suffix occurs, or how much of it is also a prefix.
- Line the pattern up and compare right to left.
- On a full match, record the occurrence and shift by the good-suffix rule for the empty mismatch.
- On a mismatch, ask both tables and take the larger of the two distances, never less than one.
Worth noticing
- The two tables often disagree, and the frame that shifts says both numbers. Watching which one wins is the whole reason this page is separate from Horspool’s.
- The good-suffix table is the piece almost every explanation asserts rather than derives. It is built here one step at a time, over the reversed pattern’s borders, for exactly that reason.
- The bad-character rule can produce a negative distance — when the offending character appears to the right of where it mismatched — which is why the shift is floored at one. Without the floor the search would move backwards.
Cost
- Best
- O(n / m)
- Average
- O(n)
- Worst
- O(n · m)
- Extra space
- O(m + alphabet)
- Longest text
- 160 characters
- Longest pattern
- 24 characters
The limits are pedagogical rather than technical: one column is drawn per character, and a run has to stay short enough to sit and watch. A text and pattern that would take more than three thousand steps on this algorithm are refused before a single step is generated — and because that depends on the text itself and not only on its length, the tool counts the steps first rather than guessing from a formula.