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

Rabin-Karp

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 
 
 
 
 
  
 
 
Rabin-Karp String Matching
  
 
  Elementary (2/5)
 
~45 minutos   Rolling hash  Hash collision handling  O(n+m) average case  Multiple pattern matching  
Prereqs: String manipulation, Modular arithmetic  
 
Quick Reference
Rabin-Karp
Rabin-Karp hashes the pattern and every length-m window of the text using a rolling hash, comparing hashes first. Only when a hash collision occurs does it verify the actual characters, so most windows are skipped in constant time.

Difficulty: Elementary (2/5)
string
Complexity
Best Time
O(n + m)
Average Time
O(n + m)
Worst Time
O(n·m)
Space
O(1)
When to Use
Use Rabin-Karp when you need to search for multiple patterns at once (each window hash can be compared against many pattern hashes), or when the text is dominated by rare hash collisions.
Pros
  • Rolling hash slides in O(1) per window
  • Extends naturally to multi-pattern search
  • Constant extra space
Cons
  • Worst case O(n·m) with many collisions
  • Hash collision requires character verification
  • Choosing the base and modulus matters
History
Rabin-Karp was published in 1987 by Michael Rabin and Richard Karp. Its rolling-hash idea came directly out of the randomized-hashing work in string matching, and it is the basis of substring-hash tricks used in competitive programming.
 
 
Rabin-Karp es un algoritmo de string matching basado en rolling hash: calcula hashes del texto en una sliding window y compara con el hash del patrón. Si los hashes coinciden, verifica carácter por carácter para confirmar.


Es especialmente útil para múltiples patrones o detección de plagio (comparar todos los substrings de longitud m).


Cómo Funciona


    

  1. Calcula hash del patrón: hash_pat = Σ pat[i] × base^{m-1-i} mod mod.
    2. 

  2. Calcula hash de la primera ventana del texto: hash_window para text[0..m-1].
    3. 

  3. Rolling: para cada posición i de 1 a n-m:

      

    • hash_window = (hash_window - text[i-1] × base^{m-1}) × base + text[i+m-1] mod mod
      • 

    • Si hash_window == hash_pat: verifica carácter por carácter.
      • 

    

    4. 

  4. Si verificación pasa: match encontrado.
    5. 



Idea Clave


El rolling hash permite actualizar el hash de la ventana en O(1): eliminas el carácter más viejo (multiplicado por base^{m-1}), multiplicas el resto por base, y añades el nuevo carácter.


Colisiones son posibles (dos strings distintas con el mismo hash), por lo que siempre necesitas verificación lineal tras una coincidencia de hash.


Ejemplo Trabajado


Patrón: ABC, texto: ABABC.


Elige base = 256, mod = 101.


Hash del patrón ABC:


hash('A') = 65
hash('B') = 66
hash('C') = 67

hash_pat = (65 × 256² + 66 × 256¹ + 67) mod 101


Ventana 1 ABA (índices 0-2): calcula hash y compara.
Rolling a ventana 2 BAB (índices 1-3): actualiza hash.
Rolling a ventana 3 ABC (índices 2-4): actualiza hash → coincide → verifica → match.


Casos Extremos y Trampas


    

  • Colisiones — con mod pequeño, colisiones son frecuentes. Usa mod grande (10⁹+7) o doble hash.
    • 

  • Overflow — usa mod para evitar overflow en lenguajes con enteros limitados.
    • 

  • Patrón vacío — indefinido; retorna 0 o error.
    • 

  • Múltiples patrones — calcula hash para cada patrón, usa hash set para lookup O(1).
    • 



Comparación





































AlgoritmoTiempo promedioBacktrack textoMúltiples patrones
NaiveO(nm)SíNo
KMPO(n+m)NoNo
Rabin-KarpO(n+m)NoSí (hash set)
Boyer-MooreO(n/m)NoNo


Aplicaciones


    

  • Detección de plagio — busca todos los substrings de longitud m en un corpus
    • 

  • Búsqueda en documentos — encuentra múltiples palabras clave
    • 

  • Bioinformática — búsqueda de secuencias en genomas grandes
    • 

  • Enseñanza — introduce rolling hash y probabilidad de colisión
    • 



Trayectoria de Práctica


    

  1. Implementa rolling hash con base=256, mod=101; traza el ejemplo.
    2. 

  2. Añade verificación carácter por carácter tras coincidencia de hash.
    3. 

  3. Investiga double hashing: ¿cómo reduce colisiones?
    4. 

  4. Extiende a múltiples patrones: almacena hashes en un set.
    5. 

  5. Investiga Rabin-Karp para 2D pattern matching en imágenes.
    6.