Función Z para buscar patrones
Compare prefijos a lo largo de la cadena
Función Z para buscar patrones es una lección gratuita de Competitive Programming Academy en CoddyKit. Esta es la lección 3 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de Competitive Programming Academy, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Competitive Programming Academy incluye 4 lecciones en total.
Otra herramienta de coincidencia
La función Z es una alternativa clara a KMP para buscar patrones. A muchas personas les resulta más fácil de entender. ✨
Qué significa z[i]
Para cada índice, z[i] es la longitud de la subcadena más larga que comienza en i y que también coincide con un prefijo de la cadena completa.
Un pequeño ejemplo
Para aabaab, z es 0,1,0,3,1,0. En el índice 3, el segmento aab coincide con el prefijo, por lo que su longitud es 3.
La caja Z
Seguimos una ventana [l, r], que representa la coincidencia más a la derecha encontrada hasta el momento. Esto permite reutilizar comparaciones anteriores.
l, r = 0, 0Dentro de la caja
Cuando i está dentro de la caja, puede copiar un valor z conocido como punto de partida, limitado por el borde de la caja.
if i < r:
z[i] = min(r - i, z[i - l])Extenderse más allá de la caja
Después de ese punto de partida, siga comparando los caracteres uno a uno mientras coincidan con el prefijo.
while i + z[i] < n and s[z[i]] == s[i + z[i]]:
z[i] += 1Desplazar la caja hacia delante
Si la coincidencia llega más a la derecha, actualice l y r para que los índices posteriores puedan reutilizarla.
if i + z[i] > r:
l, r = i, i + z[i]Garantía de tiempo lineal
La caja solo se desplaza hacia la derecha, por lo que el trabajo total es O(n). Cada carácter contribuye una cantidad acotada.
Buscar con Z
Concatene pattern + sep + text y ejecute Z. Cualquier valor z igual a la longitud del patrón indica una coincidencia.
combined = pattern + chr(0) + text
z = z_function(combined)Leer las coincidencias
Recorra el arreglo Z; dondequiera que z[i] == len(pattern), la coincidencia comienza en la posición correspondiente del texto.
if z[i] == len(pattern):
matches.append(i - len(pattern) - 1)Z frente a KMP
Z y KMP se ejecutan en tiempo lineal. Z suele ser más sencilla de programar, así que es una excelente alternativa en su arsenal.
Comprobación rápida
Asegúrese de haber comprendido bien el significado del arreglo Z.
Repaso: ventajas de la función Z
Ha construido el arreglo Z con una caja deslizante, ha buscado en tiempo lineal y ahora tiene una alternativa clara a KMP. 🎯
Preguntas frecuentes
¿La lección «Función Z para buscar patrones» es gratis?
Sí — el texto completo de «Función Z para buscar patrones» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de Competitive Programming Academy, actualiza a CoddyKit PRO. El curso de Competitive Programming Academy incluye 4 lecciones en total.
¿Qué aprenderé en «Función Z para buscar patrones»?
Compare prefijos a lo largo de la cadena Practicas Competitive Programming Academy con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar Competitive Programming Academy?
No se requiere experiencia previa. Competitive Programming Academy en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 3 de 4.
¿Cuánto tiempo toma la lección «Función Z para buscar patrones»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de Competitive Programming Academy?
Sí. Cada lección de Competitive Programming Academy incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- Función de prefijo de KMP
- Hash polinómico de cadenas
- Función Z para buscar patrones
- Tries para búsquedas por prefijo