Introducción

El Algoritmo Z (también conocido como Z‑function) es una técnica lineal para procesar cadenas de texto que permite, entre otras cosas, buscar patrones en O(n) tiempo. Su principal ventaja frente a algoritmos clásicos como la búsqueda ingenua es que construye una tabla que captura la longitud del prefijo más largo que coincide con el substrings a partir de cada posición.

Este artículo muestra cómo funciona el algoritmo, cómo implementarlo en Python 3.12+ y cómo aplicarlo a problemas reales de búsqueda de patrones y procesamiento de textos.

¿Cómo funciona el Algoritmo Z?

Para una cadena S de longitud n, el vector Z[i] (con i > 0) representa la longitud del prefijo más largo de S que también es un prefijo de la subcadena que comienza en i. Formalmente:

Z[i] = max { k | S[0..k‑1] = S[i..i+k‑1] }

El algoritmo mantiene dos punteros:

• l – límite izquierdo del segmento z‑box actual.
• r – límite derecho del mismo segmento.

Con estos punteros, la construcción de Z se realiza en tiempo lineal, reutilizando comparaciones ya realizadas.

Implementación paso a paso en Python

A continuación se muestra una implementación clara y optimizada del Algoritmo Z.

def z_function(s: str) -> list[int]:
    """Calcula el vector Z de la cadena s.
    Complejidad: O(|s|)
    """
    n = len(s)
    z = [0] * n
    l = r = 0  # límites del Z‑box actual
    for i in range(1, n):
        if i <= r:
            # i está dentro del Z‑box; usamos un valor pre‑calculado
            z[i] = min(r - i + 1, z[i - l])
        # Intentamos extender el Z‑box desde la posición i
        while i + z[i] < n and s[z[i]] == s[i + z[i]]:
            z[i] += 1
        # Si la extensión supera el Z‑box actual, actualizamos l y r
        if i + z[i] - 1 > r:
            l, r = i, i + z[i] - 1
    return z

Esta función devuelve una lista donde z[0] siempre es 0 (por convención). Si necesitas que z[0] = n, basta con asignarlo después de la llamada.

Ejemplos prácticos

Veamos tres casos de uso comunes: búsqueda de patrón, detección de repeticiones y cálculo de periodos.

def z_search(text: str, pattern: str) -> list[int]:
    """Devuelve los índices donde pattern aparece en text."""
    concat = pattern + "$" + text  # '$' es un separador que no aparece en el alfabeto
    z = z_function(concat)
    m = len(pattern)
    result = []
    for i in range(m + 1, len(concat)):
        if z[i] == m:
            result.append(i - m - 1)  # posición en el texto original
    return result
# Ejemplo de ejecución
text = "abracadabraabracadabra"
pat = "abr"
print(z_search(text, pat))  # → [0, 7, 14]

def longest_repeated_substring(s: str) -> str:
    z = z_function(s)
    max_len = max(z)
    if max_len == 0:
        return ""
    idx = z.index(max_len)
    return s[idx:idx + max_len]
print(longest_repeated_substring("banana"))  # → "ana"

def minimal_period(s: str) -> int:
    n = len(s)
    z = z_function(s)
    for i in range(1, n):
        if i + z[i] == n and n % i == 0:
            return i
    return n
print(minimal_period("abcabcabc"))  # → 3

Comparativa: Algoritmo Z vs. KMP y Suffix Array

Buenas prácticas, optimización y troubleshooting

• Evita concatenaciones costosas: usa ''.join([...]) o f"{pat}\0{txt}" para evitar copias innecesarias.
• Usa memoryview o bytearray si trabajas con datos binarios; el algoritmo funciona idénticamente en bytes.
• Profiling: cProfile o timeit para validar que la complejidad se mantiene lineal en casos de peor‑caso (e.g., "a"*10⁶ + "b").
• Seguridad: nunca confíes en el separador ($) si el alfabeto del usuario lo incluye; elige un carácter fuera del rango Unicode del input o usa una longitud de separador segura.
• Escalabilidad: para volúmenes de datos que superen la RAM, procesa bloques y reutiliza el Z‑vector parcial mediante técnicas de “streaming Z‑function”. Bibliotecas como numpy pueden acelerar comparaciones vectorizadas.

Conclusión

El Algoritmo Z es una herramienta poderosa y ligera para el procesamiento de cadenas. Su implementación en Python es corta, fácil de leer y mantiene la garantía de O(n) en tiempo y espacio. Con los ejemplos y comparativas presentados, ya puedes incorporar el Z‑algorithm en tus proyectos de búsqueda de texto, análisis de repeticiones y detección de periodos, eligiendo la solución más adecuada según la naturaleza de tu problema.