BM

BM (Boyer–Moore)

BM is named after its inventors, Bob Boyer and J. Strother Moore. To reduce comparisons, it uses two rules:

• The bad-character rule

• The good-suffix rule

Bad-character rule

A bad character is a text character that mismatches the aligned pattern character.

Why is the bad character not the T at text index 2? Would that position not be examined first?

BM compares from the rightmost character toward the left. Once the first mismatch is found, the pattern need not move one position at a time. A match is possible only if the pattern character aligned with the bad character is the same. Since pattern index 1 is also T, align that T with the text's bad character for the next attempt.

A mismatch farther to the right may allow a larger shift, saving more comparisons. This is why BM scans from right to left.

Next, GCG matches from right to left, followed by a mismatch at text character A.

Similarly, align the A at pattern index 2 with the text's bad character.

If the bad character does not occur in the pattern, move the pattern to the position immediately after it in the text.

Good-suffix rule

A good suffix is a suffix that has matched between the text and the pattern.

For the following example, the bad-character rule alone would shift the pattern only one position.

The good-suffix rule can reduce comparisons further. In the first attempt, both the text and pattern share the matched suffix GCG. If another occurrence of GCG exists earlier in the pattern, and its preceding character differs from the original mismatching pattern character, align that occurrence with the good suffix.

If no other occurrence exists, can the pattern simply move past the whole good suffix?

No. Check whether a pattern prefix matches a suffix of the good suffix, so the shift does not skip a possible match.

When should the bad-character or good-suffix rule be used?

After each comparison round, compute both shifts and choose the larger. If the bad-character rule permits three positions and the good-suffix rule permits five, use the good-suffix shift.