Overview
Boyer-Moore uses mismatch information to shift the pattern farther than one character when possible.
CoreSource checked
Boyer-Moore
Searches text by comparing from the end of the pattern and making large skips.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Pattern Matching
- Difficulty
- Intermediate
- Family
- Skip-Based Matching
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 1
- Relationships
- 5
- Code example
- Ready
- Visualization
- Ready
Core Concepts
right-to-left comparisonbad-character shiftgood-suffix shiftskip distancepattern comparisonstring sequenceheuristic estimateskip-based matching
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n / m)
Average
O(n)
Worst
O(nm)
Space
O(m + a)
When to Use
- Use Boyer-Moore when you need to compare pattern characters from right to left.
- Use it for fast exact text search with inputs like text.
- Use it when exact, fuzzy, or structured patterns must be found in sequences.
- Use it when the Skip-Based Matching tradeoff is acceptable for the problem size.
When Not to Use
- Avoid it when preprocessing cost is larger than a one-off simple scan.
- Do not treat the O(n) average case as a guarantee; check the O(nm) worst case.
- Avoid it when the required output is not match positions.
What It Does
- Compares pattern characters from right to left
- Skips alignments using precomputed rules
Use Cases
- Fast exact text search
- Searching long text
- String matching libraries
Inputs
- Text
- Pattern
Outputs
- Match positions
Key Formulas (1)
Bad-character shift
shift = max(1, mismatchindex − lastindex of(mismatchedchar))
shift = max(1, mismatch_index - last_index_of(mismatched_char))Skips alignments based on the mismatched character's last position in the pattern.
Pseudocode
- 1.Precompute bad-character and good-suffix shift tables
- 2.Align the pattern with the text
- 3.Compare from the pattern's last character backward
- 4.If a mismatch occurs, choose a safe shift
- 5.Record a match when all characters match
Canonical Example
- Input
- text = "HERE IS A SIMPLE EXAMPLE", pattern = "EXAMPLE"
- Output
- match at index 17
- Explanation
- Right-to-left comparisons and shift tables skip alignments that cannot match.
Implementation Notes
- Precompute bad-character and good-suffix tables before scanning.
- Compare the pattern from right to left at each alignment.
- After a match or mismatch, shift by the maximum safe rule.
Common Pitfalls
- Building bad-character shifts with the wrong occurrence positions.
- Forgetting that good-suffix and bad-character rules must not skip valid matches.
- Ignoring short patterns where preprocessing overhead may dominate.
Interactive Mechanism Walkthrough
Indexed Interval & Boundary ProbeShow the pattern jumping over sections of text after mismatches.
Target key: 41low=0, mid=4, high=9
4[0]
9[1]
15[2]
22[3]
27[4]
34[5]
41[6]
49[7]
58[8]
63[9]
Step 1 of 5: Precompute bad-character and good-suffix shift tables
string-skip-searchNotes
Boyer-Moore is especially effective with longer patterns and larger alphabets.
Sources (2)
What each reference supports for this entry.
Algorithms on Strings, Trees, and Sequences
BookString algorithms reference for Boyer-Moore's pattern matching, suffix indexing, alignment, or sequence-processing mechanism.
Open sourceIntroduction to Algorithms (CLRS)
BookTextbook support for Boyer-Moore's algorithm family, complexity framing, and standard implementation concepts.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageAlternative toKnuth-Morris-Pratt
Boyer-Moore skips ahead using bad-character and good-suffix rules.
Conceptual neighborWu-Manber
Wu-Manber extends skip-table ideas to multi-pattern matching.
Related Algorithms
Tags
Pattern MatchingStringsHeuristic