Saltar al contenido 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

Paso 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 String Matching
  
 
  Intermediate (3/5)
 
~1.5 horas   Right-to-left matching  Bad character heuristic  Good suffix heuristic  O(n/m) best case  
Prereqs: String manipulation, KMP algorithm  
 
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.
 
 
Boyer-Moore es el algoritmo de string matching más rápido en la práctica: compara el patrón de derecha a izquierda y puede saltar múltiples posiciones en el texto tras un mismatch usando dos heurísticas.


Es especialmente efectivo cuando el patrón es largo o el alfabeto es grande, porque el O(n/m) caso promedio es muy rápido.


Cómo Funciona


Alinea patrón con texto desde posición i.
Compara patrón right-to-left desde j = m-1.


    

  1. Matching: mientras text[i+j] == pat[j], decrementa j.
    2. 

  2. Match completo: si j < 0, encontrado en i.
    3. 

  3. Mismatch en j: calcula shift.

      

    • Bad character: si text[i+j] no está en patrón, salta j+1. Si está, salta j - last_occurrence[text[i+j]].
      • 

    • Good suffix: si hay suffix que coincide, salta según tabla.
      • 

    

    4. 

  4. Shift: i += max(bad_char_shift, good_suffix_shift).
    5. 



Idea Clave


Right-to-left permite saltos grandes: si el primer carácter comparado (el más a la derecha del patrón) no coincide, puedes saltar todo el patrón si ese carácter no aparece en él.


Las dos heurísticas son independientes y se combinan tomando el máximo shift.


Ejemplo Trabajado


Patrón: EXAMPLE, texto: FINISH EXAMPLE CODE.


Alinea EXAMPLE con FINISH (primeras 7 chars).


    

  • Compara right-to-left: E vs H → mismatch.
    • 

  • Bad character: H no está en EXAMPLE → shift = 7 (salta todo el patrón).
    • 



Alinea con EXAMPLE en texto: match completo.


Casos Extremos y Trampas


    

  • Patrón repetitivo — AAAAA en texto AAAAAAAAA: worst case O(nm).
    • 

  • Alfabeto pequeño — si todas las letras aparecen en el patrón, bad character hace saltos pequeños.
    • 

  • Good suffix — complementa bad character cuando el carácter sí aparece pero el suffix coincide.
    • 

  • Horspool — simplificación que solo usa bad character; más simple, casi igual de rápido.
    • 



Comparación





































AlgoritmoDirecciónComplejidad promedioComplejidad worst
NaiveLeft-to-rightO(nm)O(nm)
KMPLeft-to-rightO(n+m)O(n+m)
Boyer-MooreRight-to-leftO(n)O(nm)
HorspoolRight-to-leftO(n)O(nm)


Aplicaciones


    

  • Editores de texto — grep, find/replace
    • 

  • Detección de virus — escaneo rápido de firmas
    • 

  • Detección de plagio — búsqueda eficiente en corpus grandes
    • 

  • Enseñanza — introduce heurísticas y right-to-left matching
    • 



Trayectoria de Práctica


    

  1. Investiga Horspool (solo bad character); implementa y prueba.
    2. 

  2. Investiga Boyer-Moore completo con good suffix.
    3. 

  3. Compara con KMP en texto aleatorio vs texto repetitivo.
    4. 

  4. ¿Por qué right-to-left es más rápido en promedio?
    5. 

  5. Investiga Apostolico-Giancarlo: ¿cómo mejora good suffix?
    6.