Contador de pasos de búsqueda KMP | Tabla de fallos y ahorro de pasos a la vista
Observa cómo trabaja el algoritmo Knuth-Morris-Pratt sobre tu propio texto. Esta herramienta construye la tabla de la función de fallo LPS de tu patrón, ejecuta el recorrido KMP en tiempo lineal y cuenta cuántas comparaciones de caracteres necesita KMP frente a una búsqueda ingenua de doble bucle sobre la misma entrada.
💡 Sobre esta herramienta
La mayoría de las explicaciones de KMP se quedan en "es O(n+m), créelo". Eso deja un hueco: puedes recitar la cota de complejidad sin sentir de dónde viene el ahorro ni por qué importa la función de fallo. Y cuando te toca implementar KMP en una práctica o en una entrevista, la tabla LPS es justo la parte que confunde.
Este contador cierra ese hueco con números concretos de tu entrada. Escribe cualquier patrón y texto, y verás el arreglo LPS fila por fila (i, p[i], lps[i]), las posiciones exactas de coincidencia y el conteo de comparaciones cara a cara. Como las cifras de KMP y de la búsqueda ingenua salen del mismo texto, puedes encontrar tú mismo el punto de equilibrio: en texto aleatorio la diferencia es pequeña, pero con un patrón como aaaab contra una larga cadena de a, la búsqueda ingenua se dispara mientras KMP permanece lineal. Ese contraste es la esencia del algoritmo, y aquí lo reproduces cuando quieras.
🧐 Preguntas frecuentes
¿Qué guarda en realidad la tabla LPS?
LPS[i] es la longitud del prefijo propio más largo de p[0..i] que también es sufijo de p[0..i]. Ante un desajuste, KMP salta el puntero del patrón a LPS[j-1] en lugar de reiniciar en cero, y eso es lo que elimina las comparaciones redundantes.
¿Cómo se cuenta aquí una "comparación"? Un paso equivale a una comparación entre un carácter del patrón y uno del texto. Los retrocesos de puntero que KMP hace a través de la tabla LPS no se cuentan como pasos, porque no tocan ningún carácter del texto. La búsqueda ingenua cuenta cada comparación del bucle interno.
¿Por qué a veces la aceleración apenas supera 1x? En texto natural o aleatorio los desajustes suelen ocurrir en el primer carácter, así que la búsqueda ingenua rara vez retrocede mucho. La ventaja de KMP aparece con patrones de prefijos repetidos largos sobre texto adversario, donde la búsqueda ingenua reexamina los mismos caracteres muchas veces.
¿Detecta coincidencias solapadas?
Sí. Tras una coincidencia completa KMP reinicia j a LPS[m-1], por lo que las apariciones solapadas (como aa dentro de aaaa) se reportan todas. Los índices son base 0.
¿Cuentan los espacios y los símbolos? Sí. La búsqueda es a nivel de carácter, así que espacios, saltos de línea y puntuación se comparan tal cual. No hay límite de longitud en ningún campo, aunque los patrones más cortos construyen su tabla LPS más rápido.
📚 Datos curiosos
KMP fue publicado en 1977 por Donald Knuth, James Morris y Vaughan Pratt. Antes de KMP, el enfoque estándar era la búsqueda ingenua, cuyo peor caso es O(n·m): basta una entrada como un patrón de casi-todo-iguales contra un texto de casi-todo-iguales para que el número de comparaciones crezca de forma cuadrática. La función de fallo es, en esencia, un pequeño autómata finito compilado a partir del patrón. La misma idea de la función prefijo reaparece lejos de la búsqueda de cadenas: sostiene técnicas de programación competitiva como contar los bordes distintos de una cadena o hallar el periodo mínimo de una secuencia repetida.