Pular para o conteúdo principal
Interactive Algorithm Education

Visualize & Master Algorithms & Data Structures

Explore classic & modern sorting algorithms, efficient searching techniques, and interactive data structure visualizations — all with real-time step-by-step animation, comparisons, swaps, and Big-O metrics.

String Matching Visualizer

Boyer-Moore

Passo 0 / 0
Speed 100ms
Step Progress 0 / 0
Comparisons 0
Matches Found 0
Status Ready
Text / Pattern
Comparing
Matched
Window / Aux highlight
Match found
Step Explanation

Select an algorithm and press Play to watch the pattern slide across the text.

—
Pseudocode 
 
 
 
 
  
 
 
Boyer-Moore
  
 
  Intermediate (3/5)
 
~45 minutes   Right-to-left pattern scanning  Bad-character shift rule  Last-occurrence table  Sublinear average case  
Prereqs: String matching basics, KMP or naive pattern matching  
 
Quick Reference
Boyer-Moore
Boyer-Moore scans the pattern right-to-left and shifts the window using the last-occurrence (bad-character) rule and the good-suffix rule. When the text alphabet is large, most characters fail on the first probe and the pattern jumps quickly.

Difficulty: Intermediate (3/5)
string
Complexity
Best Time
O(n/m)
Average Time
O(n)
Worst Time
O(nm)
Space
O(m)
When to Use
Use for fast substring search over large alphabets — text editors, grep-style tools, and intrusion/pattern detection where the pattern is much shorter than the text.
Pros
  • Sublinear average case — often skips text characters
  • Excellent for large alphabets
  • Two independent shifting rules can be combined
Cons
  • Worst case is O(nm) without the strong good-suffix rule
  • Bad-character table needs the alphabet size
  • Overkill for tiny patterns
History
Boyer-Moore was published by Robert S. Boyer and J Strother Moore in 1977, shortly after KMP. Its right-to-left scanning and bad-character heuristic made it the fastest pattern matcher in practice for decades, and variants still power modern search tools.
 
 
KMP guarantees linear time by never backing up the text pointer. Boyer-Moore takes the opposite bet: compare the pattern from the right, and when a character mismatches, skip ahead as far as that character allows. When the alphabet is large and the pattern is short, most windows fail on their last character — so the pattern jumps many positions per comparison and often runs faster than linear.


How It Works


    

  1. Precompute the last-occurrence table — for every character, the rightmost index where it appears in the pattern. Characters that don’t appear get -1.
    2. 

  2. Align the pattern under the text and compare characters from right to left.
    3. 

  3. On a mismatch at pattern position j against text character c, shift the window right by:

    shift = j - last[c]
    
If c appears in the pattern at position last[c], this aligns that occurrence with the mismatch. If c is absent (last[c] = -1), the whole window slides past the mismatch.
    4. 

  4. On a full match, record the position and shift by 1 to keep scanning.
    5. 



Key Insight


The bad-character rule exploits negative information: seeing a text character that isn’t in the pattern at all lets the window skip the entire pattern length in one step. And because scanning starts at the right edge, a mismatch almost always happens after just one comparison — so on typical text the number of text characters actually examined is far below n.


Worked Example


The visualizer searches for P = EXAMPLE in the classic text T = THIS IS A SIMPLE EXAMPLE.


The last-occurrence table is built from the pattern:

























charEXAMPL
last612345


Alignment 1: EXAMPLE placed under THIS IS — the first right-edge comparison fails (S vs E). Since S never appears in the pattern, the window jumps 7 positions to just after the S. Later, alignment at SIMPLE fails at E vs M; M appears at pattern index 3, so the shift is 6 − 3 = 3, which lands EXAMPLE exactly on EXAMPLE — a full match at position 17.


Edge Cases & Pitfalls


    

  • Shift ≤ 0: if the mismatching character’s last occurrence is to the right of j, j - last[c] can be ≤ 0. Guard with max(1, shift).
    • 

  • Pattern longer than text: trivially no matches; the main loop guard i <= n - m handles it.
    • 

  • Worst case: repetitive patterns on small alphabets (e.g. pattern of all the same character in a run) degrade to O(nm) without the good-suffix rule.
    • 

  • Good-suffix rule: the full Boyer-Moore adds a second shift table for matched suffixes; the bad-character rule alone is the “Boyer-Moore-Horspool” simplification.
    • 

  • Case sensitivity: the last-occurrence table is built over exact characters.
    • 



Comparison: Boyer-Moore vs Other Matchers





































AspectNaiveKMPBoyer-Moore
Scan directionLeft-rightLeft-rightRight-left
Average caseO(n + m)O(n)sublinear
Extra spaceO(1)O(m)O(m)
Best forTiny patternsGuaranteed linearLarge alphabets


Applications


    

  • Text search tools — grep-style search over large files
    • 

  • Editors — fast “find” with big alphabets and short patterns
    • 

  • Intrusion detection — scanning network payloads for signatures
    • 



Practice Trajectory


    

  1. Build the last-occurrence table for EXAMPLE and confirm the values above.
    2. 

  2. Trace the visualizer’s first jump past the S in THIS IS.
    3. 

  3. Explain why max(1, shift) is required for correctness.
    4. 

  4. Compare the number of character comparisons with naive scanning.
    5. 

  5. Research the good-suffix rule and why it restores the linear worst case.
    6.