1. ¿Qué es el algoritmo KMP?

El algoritmo de Knuth-Morris-Pratt (KMP) es una técnica de búsqueda de patrones en cadenas de texto que logra O(n + m) tiempo lineal, donde n es la longitud del texto y m la del patrón. Fue publicado en 1977 por Donald Knuth, James H. Morris y Vaughan Pratt.

KMP evita la retrocesión del índice del texto mediante una tabla de prefijo‑sufijo (también llamada lps – longest proper prefix which is also suffix). Esta tabla indica cuánto podemos desplazar el patrón cuando ocurre una discordancia.

2. Complejidad del algoritmo

• Tiempo de construcción de la tabla LPS: O(m)
• Tiempo de búsqueda: O(n)
• Espacio adicional: O(m) (para la tabla LPS)

En la práctica, KMP se comporta muy bien cuando el patrón contiene repeticiones internas (por ejemplo, "abab"), ya que la tabla LPS permite saltos significativos.

3. Implementación paso a paso en Python

3.1. Construcción de la tabla LPS

def build_lps(pattern: str) -> list[int]:
    """Construye la tabla LPS (Longest Prefix‑Suffix) para *pattern*.
    Args:
        pattern: Cadena del patrón a buscar.
    Returns:
        Lista de enteros con la longitud del prefijo‑sufijo para cada posición.
    """
    m = len(pattern)
    lps = [0] * m
    length = 0  # longitud del prefijo anterior más largo
    i = 1
    while i < m:
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        else:
            if length != 0:
                length = lps[length - 1]
                # No incrementamos i aquí, volvemos a comparar con el nuevo length
            else:
                lps[i] = 0
                i += 1
    return lps

3.2. Búsqueda del patrón

def kmp_search(text: str, pattern: str) -> list[int]:
    """Devuelve todas las posiciones donde *pattern* aparece en *text* usando KMP.
    Args:
        text: Cadena donde buscar.
        pattern: Patrón a encontrar.
    Returns:
        Lista de índices (0‑based) donde el patrón comienza.
    """
    n, m = len(text), len(pattern)
    if m == 0:
        return []
    lps = build_lps(pattern)
    i = j = 0  # i recorre el texto, j recorre el patrón
    matches = []
    while i < n:
        if text[i] == pattern[j]:
            i += 1
            j += 1
            if j == m:
                matches.append(i - j)
                j = lps[j - 1]  # Continuar buscando posibles solapamientos
        else:
            if j != 0:
                j = lps[j - 1]
            else:
                i += 1
    return matches

Ejemplo de uso:

text = "abxabcabcaby"
pattern = "abcaby"
print(kmp_search(text, pattern))  # salida: [6]

4. KMP vs. Boyer‑Moore y Rabin‑Karp

En entornos donde la longitud del patrón es relativamente pequeña y el texto es grande, KMP ofrece una garantía de tiempo lineal sin depender de heurísticas, lo que lo hace ideal para sistemas embebidos o aplicaciones de tiempo real.

5. Aplicaciones prácticas de KMP

• Compiladores y analizadores léxicos: detección de tokens y patrones sintácticos.
• Plataformas de seguridad: escaneo de firmas de malware en flujos de datos.
• Bioinformática: búsqueda de motivos genéticos en ADN/ARN.
• Sistemas de logging: filtrado de eventos críticos en tiempo real.

6. Optimización y mejores prácticas

6.1. Reutilizar la tabla LPS

Si vas a buscar el mismo patrón en varios textos, calcula lps una sola vez y reutilízalo. Reduce la complejidad total a O(k·n + m) para k búsquedas.

6.2. Evitar conversiones de tipo innecesarias

Trabaja siempre con str nativas de Python (UTF‑8) y evita .encode()/.decode() dentro del bucle de búsqueda.

6.3. Uso de memoryview para datos binarios

Para textos muy grandes (GBs) en entornos de alto rendimiento, conviértelos a bytes y usa memoryview para evitar copias.

def kmp_search_bytes(text: bytes, pattern: bytes) -> list[int]:
    # implementación idéntica pero usando memoryview para indexación rápida
    ...

7. Solución de problemas comunes

• Patrón vacío: la función devuelve []. Si deseas que coincida en todas las posiciones, maneja el caso por separado.
• Unicode y normalización: asegúrate de normalizar ambas cadenas con unicodedata.normalize('NFC', s) antes de buscar.
• Desbordamiento de índices: la tabla LPS nunca contiene valores mayores que len(pattern)-1, por lo que los accesos son seguros.

8. Compatibilidad y escalabilidad

KMP es independiente de la plataforma; funciona igual en CPython, PyPy, Jython o en entornos de contenedores Docker. Para cargas masivas, considera ejecutar la búsqueda en procesos paralelos usando multiprocessing.Pool o en un clúster Spark con pyspark (aunque la sobrecarga de serialización puede superar los beneficios para patrones muy pequeños).

8.1. Benchmark rápido

import time, random, string
def rand_str(n):
    return ''.join(random.choices(string.ascii_lowercase, k=n))
text = rand_str(10_000_000)
pattern = 'abcde'
start = time.perf_counter()
_ = kmp_search(text, pattern)
print('KMP elapsed:', time.perf_counter() - start)

En máquinas modernas con CPU de 3 GHz, el tiempo suele estar entre 0.05 s y 0.12 s para 10 M de caracteres.

9. Conclusión

El algoritmo Knuth‑Morris‑Pratt sigue siendo una herramienta esencial para la búsqueda de patrones linealmente garantizada. Su implementación en Python es sencilla, pero su comprensión profunda permite adaptarlo a contextos de alto rendimiento, sistemas embebidos o pipelines de datos masivos.

Al combinar KMP con buenas prácticas de gestión de memoria, reutilización de la tabla LPS y paralelismo controlado, puedes obtener una solución de búsqueda robusta, predecible y escalable.