Rabin-Karp y rolling hash

Compara NÚMEROS, no cadenas. Hashea cada ventana; un rolling hash lo actualiza en O(1) por deslizamiento.

El rolling hash

• Lee una cadena como un número en base B mod un primo grande
• Desliza la ventana: saca el carácter que sale, recorre, suma el que entra
• H' = ((H − s[i]·Bᵐ⁻¹)·B + s[i+m]) mod M — tres operaciones, O(1)
• Comparar dos hashes es O(1) sin importar la longitud del patrón

Mira rodar el hash

Verde = carácter que acaba de entrar · rojo = carácter que acaba de salir (módulo de juguete 101). 'abc' hashea a 22; la ventana llega a 22 → verifica → match en 5.

Superpoder: muchos patrones, una pasada

Checa el hash de cada ventana contra un CONJUNTO de k hashes de patrones. 800 patrones: 200× más rápido que KMP×800.

Probabilístico, así que verifica

• Una coincidencia de hash solo es PROBABLE → confirma con una revisión de caracteres
• Módulo primo grande (~2⁶¹) → probabilidad de colisión ~10⁻¹⁸ (cero vistas en 2000 búsquedas)
• Módulo chico o predecible → hash flooding → O(n·m)
• El hash es un filtro, no una prueba

Para llevar

La aleatorización + el hashing te compran CAPACIDADES: fingerprint, dedup, comparación en lote. El rolling hash acabó siendo más grande que el algoritmo — rsync, chunking de respaldos, plagio, git. Siguiente: Boyer-Moore — escanea de derecha a izquierda, salta hacia adelante, lee menos de n caracteres.