Boyer-Moore

Boyer-Moore matching with the bad character rule.

Boyer-Moore

Boyer-Moore scans the pattern from right to left. This direction allows large shifts; in many cases only a small part of the text is examined.

It uses two rules: bad character and good suffix. We focus on the bad character rule here.

The bad character rule shifts the pattern according to the text character that caused the mismatch, aligning that character with the pattern.

Bad character table

The bad character table stores the last occurrence index in the pattern for each character. On a mismatch, the shift amount is max(1, j - bad[text[i]]).

If the mismatched character is not in the pattern, we shift the pattern completely past it. The table is a preprocessing step built in O(m + |alphabet|) time.

This rule alone runs fast in most practical cases.

Exercise boyer_moore function

Write boyer_moore(text, pattern). Return the first match index, or -1. Print 11 with print(boyer_moore("konfeksiyonmakine", "makine")).

Show example solution

def boyer_moore(text, pattern):
    # Search with the bad character rule
    n, m = len(text), len(pattern)
    if m == 0:
        return 0
    bad = {}
    for i in range(m):
        bad[pattern[i]] = i
    i = 0
    while i <= n - m:
        j = m - 1
        while j >= 0 and pattern[j] == text[i + j]:
            j -= 1
        if j < 0:
            return i
        shift = j - bad.get(text[i + j], -1)
        if shift < 1:
            shift = 1
        i += shift
    return -1
print(boyer_moore("konfeksiyonmakine", "makine"))

Test yourself

Boyer-Moore concepts

right to left

Scan direction
bad character

Shift rule
good suffix

Second rule
large shift

Speed advantage
What does the bad character rule do?
```
shift = j - bad.get(text[i+j], -1)
```
- Rebuilds the table
- Shifts the pattern by one step
- Cancels the match
- Shifts based on the mismatched character
Show answer

Shifts based on the mismatched character — The bad character rule shifts based on the mismatched character.

bad character shift

shift = j - bad.get(text[i + j], ____)

Show answer

shift = j - bad.get(text[i + j], -1)

Next lesson: Z-algorithm

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies