Búsqueda de cadenas KMP explicada: cómo funciona, código y complejidad

Qué problema resuelve KMP

La búsqueda de cadenas pregunta en qué lugares de un texto más largo aparece un patrón corto. El método ingenuo prueba cada posición de inicio y compara los caracteres uno a uno. En texto normal es rápido, pero con entradas repetitivas es lento: buscar aaaab en aaaaaaaaaa compara casi todo el patrón en cada posición, lo que da un tiempo O(n × m).

KMP nunca vuelve a leer un carácter del texto tras una discrepancia. Donald Knuth, James H. Morris y Vaughan Pratt lo publicaron en 1977 en "Fast Pattern Matching in Strings".

La idea en palabras sencillas

Supón que buscas el patrón ABABC, has encontrado ABAB y el siguiente carácter del texto no es C. La parte que acabas de encajar, ABAB, termina en AB, que es también como empieza el patrón. Así que ya sabes que el siguiente intento empieza con 2 caracteres coincidentes y puedes seguir comparando desde la posición 2 del patrón en lugar de empezar de cero.

La función prefijo guarda estos números. pi[i] es la longitud del prefijo propio más largo de pattern[0..i] que también es sufijo suyo (propio significa que no es la cadena entera).

Por ejemplo, pi[4] = 3 porque ABABA empieza y termina con ABA. pi[5] = 0 porque ningún prefijo de ABABAC termina en C.

Ejemplo resuelto, paso a paso

Busca el patrón ABABC (función prefijo 0, 0, 1, 2, 0) en el texto ABABABC. La variable k cuenta cuántos caracteres del patrón coinciden en este momento.

El puntero del texto avanzó 7 veces y nunca retrocedió. El método ingenuo reiniciaría en la posición 1 y volvería a comparar algunos caracteres.

Implementación en Python

def prefix_function(p):
    pi = [0] * len(p)
    k = 0
    for i in range(1, len(p)):
        while k > 0 and p[i] != p[k]:
            k = pi[k - 1]          # fall back to a shorter border
        if p[i] == p[k]:
            k += 1
        pi[i] = k
    return pi

def kmp_search(text, pattern):
    """Return the start index of every occurrence (overlaps included)."""
    if not pattern:
        return []
    pi, k, hits = prefix_function(pattern), 0, []
    for i, ch in enumerate(text):
        while k > 0 and ch != pattern[k]:
            k = pi[k - 1]
        if ch == pattern[k]:
            k += 1
        if k == len(pattern):
            hits.append(i - k + 1)
            k = pi[k - 1]          # keep going to find overlapping matches
    return hits

print(prefix_function("ABABACA"))      # [0, 0, 1, 2, 3, 0, 1]
print(kmp_search("ABABABC", "ABABC"))  # [2]
print(kmp_search("AAAAA", "AA"))       # [0, 1, 2, 3]

Complejidad temporal y espacial

El algoritmo ingenuo es O(n × m) en el peor caso, pero a menudo se acerca a O(n) en texto en lenguaje natural, por lo que la ventaja de KMP se nota sobre todo con datos repetitivos.

Variantes y errores comunes

• Error de uno en el retroceso: tras una discrepancia, asigna k = pi[k - 1], no pi[k]. pi se indexa por la última posición coincidente.
• Usar if en lugar de while para el retroceso: puede hacer falta retroceder varias veces seguidas antes de que un carácter coincida.
• Olvidar reiniciar k tras una coincidencia completa: asigna k = pi[k - 1] para encontrar coincidencias solapadas, o k = 0 para las no solapadas.
• Truco de la concatenación: calcula la función prefijo de pattern + separator + text, con un separador que no aparezca en ninguno de los dos; cada posición donde el valor es igual a m es el final de una coincidencia.
• El algoritmo Z calcula un arreglo estrechamente relacionado y también busca en O(n + m).

Cuándo usarlo y usos en el mundo real

• Problemas de entrevista: implementar strStr(), palíndromo más corto (función prefijo de s + "#" + reversed(s)), patrón de subcadena repetida, período más pequeño de una cadena (m - pi[m - 1]).
• En el mundo real: búsqueda en secuencias de ADN y en flujos de paquetes de red, donde importa el tiempo lineal en el peor caso.