Boyer-Moore
- Algorithms course
- Expert
- Lesson 15/41
- 4 min
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.
Practice boyer_moore function
Write boyer_moore(text, pattern). Return the first match index, or -1. Print 11 with print(boyer_moore("konfeksiyonmakine", "makine")).
Starter code
def boyer_moore(text, pattern):
# Search with the bad character ruleSample 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"))Expected output
11
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Boyer-Moore concepts
| Term | Meaning |
|---|---|
right to left |
Scan direction |
bad character |
Shift rule |
good suffix |
Second rule |
large shift |
Speed advantage |
2 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 Correct answer
Explanation: The bad character rule shifts based on the mismatched character.
3 bad character shift
shift = j - bad.get(text[i + j], ____)shift = j - bad.get(text[i + j], -1)Explanation: With -1 the shift is at least 1.