Función de prefijo de KMP
Encuentre un patrón en O(n + m)
Función de prefijo de KMP es una lección gratuita de Competitive Programming Academy en CoddyKit. Esta es la lección 1 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.
El problema de la búsqueda de patrones
Quiere encontrar dónde aparece un patrón pequeño dentro de un texto grande. Las comprobaciones ingenuas son lentas, así que en los concursos se premia un recorrido más inteligente. 🔍
Por qué perjudica la búsqueda ingenua
Comparar el patrón en cada posición puede costar O(n*m) de tiempo. Con entradas grandes, esto supera silenciosamente el límite de tiempo.
Conozca la función prefijo
La función prefijo mide, en cada posición, el prefijo propio más largo que también es un sufijo. Es el núcleo de KMP.
Prefijo propio y sufijo
Un prefijo o sufijo propio excluye la cadena completa. En ababa, el par coincidente más largo tiene longitud 3: aba.
Qué almacena pi[i]
Almacenamos los valores en un array llamado pi. Aquí, pi[i] es la longitud del prefijo-sufijo más largo para el segmento que termina en el índice i.
Construir pi en una pasada
Construya pi de izquierda a derecha y reutilice los valores anteriores en lugar de volver a comprobar desde cero. Esa reutilización es todo el truco.
def prefix_function(s):
pi = [0] * len(s)
return piEl bucle de retroceso
Cuando los caracteres no coinciden, retroceda a pi[k-1] en lugar de restablecer a cero. Así evita repetir trabajo.
while k > 0 and s[i] != s[k]:
k = pi[k - 1]Ampliar una coincidencia
Si los caracteres actuales coinciden, aumente la longitud en uno y regístrela. Las discrepancias cuando el valor es cero simplemente permanecen en cero.
if s[i] == s[k]:
k += 1
pi[i] = kBuscar con el truco
Para buscar un patrón en un texto, únalos como pattern + sep + text. Cualquier valor de pi igual a la longitud del patrón indica una coincidencia completa.
combined = pattern + chr(0) + text
pi = prefix_function(combined)Por qué importa el separador
El separador es un símbolo que no aparece en ninguna de las dos cadenas. Impide que las coincidencias se filtren a través de la unión y produzcan resultados falsos.
La ventaja del tiempo lineal
Tanto la construcción como la búsqueda se ejecutan en O(n + m). Cada carácter se procesa una vez, así que KMP funciona bien con entradas enormes de concursos.
Comprobación rápida
Compruebe cuánto domina lo que registra la función prefijo.
Repaso: KMP en pocas palabras
Ha aprendido la función prefijo: construir pi una vez, retroceder cuando haya discrepancias y buscar en tiempo lineal. Eso es KMP en pocas palabras. 🎯
Preguntas frecuentes
¿La lección «Función de prefijo de KMP» es gratis?
Sí — el texto completo de «Función de prefijo de KMP» 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 de prefijo de KMP»?
Encuentre un patrón en O(n + m) 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 1 de 4.
¿Cuánto tiempo toma la lección «Función de prefijo de KMP»?
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