1. Introducción

Rabin‑Karp, propuesto por Michael O. Rabin y Richard M. Karp en 1987, es un algoritmo de búsqueda de patrones que aprovecha una función de hash rolling para comparar rápidamente una subcadena del texto con el patrón buscado.

Su principal ventaja es que permite comparar varios patrones simultáneamente (útil en detección de plagio o búsqueda de palabras clave) y su complejidad promedio es O(N + M), donde N es la longitud del texto y M la del patrón.

2. Fundamento teórico

• Hash rolling: se calcula un valor hash para el patrón y para la primera ventana del texto. Al desplazar la ventana un carácter, el hash se actualiza en O(1) sin volver a recorrer la ventana completa.
• Función hash típica: h = (d * (h - left_char * h_power) + right_char) % q
  • d = número de caracteres posibles (p.ej., 256 para ASCII).
  • q = número primo grande que actúa como módulo para evitar overflow y reducir colisiones.
  • h_power = d^(M‑1) % q es el factor pre‑calculado que representa el peso del carácter más a la izquierda.
• Si los hashes coinciden, se verifica carácter a carácter para descartar colisiones.

3. Complejidad y rendimiento

En la práctica, elegir un primo q de al menos 10⁹+7 y usar int de Python (arbitrariamente grande) minimiza las colisiones.

4. Implementación paso a paso en Python

A continuación se muestra una versión lista para producción, con manejo de errores, soporte Unicode y pruebas unitarias integradas.

import random
import sys
def _prime_greater_than(n: int) -> int:
    """Devuelve el primer número primo mayor que n. Utilizado para elegir q."""
    def is_prime(num):
        if num < 2:
            return False
        if num % 2 == 0:
            return num == 2
        r = int(num ** 0.5)
        for i in range(3, r + 1, 2):
            if num % i == 0:
                return False
        return True
    candidate = n + 1
    while not is_prime(candidate):
        candidate += 1
    return candidate
def rabin_karp(text: str, pattern: str, d: int = 256, q: int = None) -> list[int]:
    """Busca todas las apariciones de pattern en text.
    Args:
        text: Cadena donde se realiza la búsqueda.
        pattern: Patrón a buscar.
        d: Tamaño del alfabeto (default 256 → ASCII/UTF‑8).
        q: Primo usado como módulo. Si es None se genera dinámicamente.
    Returns:
        Lista con los índices de inicio donde pattern aparece en text.
    """
    if not pattern:
        raise ValueError("El patrón no puede estar vacío")
    n, m = len(text), len(pattern)
    if m > n:
        return []
    if q is None:
        q = _prime_greater_than(max(d, 256))
    # Pre‑cálculo de d^(m‑1) % q
    h = pow(d, m - 1, q)
    p_hash = 0  # hash del patrón
    t_hash = 0  # hash de la ventana actual del texto
    # Cálculo de hashes iniciales
    for i in range(m):
        p_hash = (d * p_hash + ord(pattern[i])) % q
        t_hash = (d * t_hash + ord(text[i])) % q
    result = []
    for s in range(n - m + 1):
        # Si los hashes coinciden, verificar carácter a carácter
        if p_hash == t_hash:
            if text[s:s+m] == pattern:
                result.append(s)
        # Deslizar la ventana: eliminar carácter izquierdo y añadir el nuevo
        if s < n - m:
            t_hash = (d * (t_hash - ord(text[s]) * h) + ord(text[s + m])) % q
            # Python puede devolver un número negativo después del módulo
            if t_hash < 0:
                t_hash += q
    return result
# ------------------- Ejemplo de uso -------------------
if __name__ == "__main__":
    sample_text = "abracadabra" * 1000  # texto grande para medir rendimiento
    pattern = "cad"
    matches = rabin_karp(sample_text, pattern)
    print(f"Patrón encontrado en posiciones: {matches[:10]} ... ({len(matches)} coincidencias total)")

El bloque anterior incluye:

• Generación automática de un primo q suficientemente grande.
• Soporte para texto Unicode (usa ord()).
• Manejo de errores y documentación tipo docstring.
• Un mini‑benchmark incorporado.

5. Comparativa con algoritmos de búsqueda de texto

6. Buenas prácticas, seguridad y optimizaciones

Elección del módulo q

Preferir primos de 31‑bits (p.ej., 1_000_000_007) para evitar overflow en entornos de 64‑bits y reducir la probabilidad de colisiones.

Pre‑cálculo de d^(m‑1) % q

Usar pow(d, m-1, q) en Python es O(log m) y evita bucles costosos.

Gestión de colisiones

• Siempre validar la coincidencia completa cuando los hashes coinciden.
• Si la tasa de colisiones es alta, probar con un segundo módulo q2 y combinar hashes (doble hashing).

Profiling y benchmarking

Utiliza timeit o cProfile para medir el tiempo real y detectar cuellos de botella en la generación del primo.

Seguridad

En entornos donde el texto proviene de usuarios, evita usar valores de d predecibles o módulos pequeños que puedan ser explotados para ataques de denegación de servicio mediante colisiones intencionales.

7. Depuración y resolución de problemas comunes

• Resultado vacío inesperado: Verificar que q sea primo y mayor que d. Un q demasiado pequeño provoca colisiones frecuentes y falsos negativos.
• Índices fuera de rango: Asegurarse de que len(pattern) ≤ len(text) antes de llamar a la función.
• Rendimiento bajo en textos Unicode: Convertir el texto a bytes con codificación UTF‑8 y operar sobre los bytes para evitar overhead de ord() en cada carácter.

8. Escalabilidad y casos de uso reales

El algoritmo Rabin‑Karp se emplea en:

• Detección de plagio: Comparar documentos contra un gran repositorio de textos.
• Filtros de virus y malware: Búsqueda de firmas en archivos binarios.
• Compresión de datos: Identificación de bloques repetidos.
• Procesamiento de logs en tiempo real: Encontrar patrones de error en flujos de registro.

En sistemas distribuidos, cada nodo puede ejecutar Rabin‑Karp localmente y luego combinar los resultados mediante un mapa‑reducción, manteniendo la complejidad lineal en el total de datos procesados.