¿Cuál es la base teórica del algoritmo de coincidencia de patrones KMP?¿Cuál es la teoría detrás del algoritmo de coincidencia de patrones KMP?
Entiendo el algoritmo en sí mismo, pero no entiendo cómo Knuth, Morris y Pratt inventaron este algoritmo.
¿Había alguna prueba matemática?
¿Puede darnos un enlace, por favor?
El algoritmo de coincidencia KMP se basa en finite automata y funciona construyendo implícitamente la tabla de transición para un autómata que coincida con la cadena. Utilizando un preprocesamiento de la cadena a buscar en tiempo lineal muy inteligente, se puede construir un autómata coincidente, y luego se puede simular el autómata en la cuerda para buscar en tiempo lineal. El resultado neto es un algoritmo de tiempo lineal para la coincidencia de cadenas.
El autómata que se construye funciona teniendo un estado para cada cantidad de cuerda que se ha emparejado hasta ahora. De manera predeterminada, las transiciones son tales que la coincidencia del próximo personaje avanza al siguiente estado en la máquina y la lectura de una transición de caracteres inválidos vuelve al principio. Sin embargo, ciertas piezas de la cadena de búsqueda pueden compartir alguna estructura superpuesta, por lo que se agregan algunas transiciones nuevas que llevan al autómata a un estado anterior (pero no el primero) cuando se lee un carácter.
Este algoritmo se generaliza mediante el algoritmo Aho-Corasick, que crea un autómata más complejo para buscar múltiples cadenas a la vez.
que tienen an implementation of this algorithm on my personal site que contiene una extensa discusión de los detalles reales de cómo funciona el algoritmo, incluyendo una prueba de corrección, más intuición formal, detrás del algoritmo, y la explicación de cómo derivar el algoritmo a partir de primeros principios. Me tomó un tiempo armarlo, pero espero que pueda ser un buen recurso para aprender más sobre el algoritmo.
Espero que esto ayude!
Morris descubrió el algoritmo desde los primeros principios, pero Knuth aprendió independientemente acerca de un teorema debido a Stephen A. Cook que el autómata pushdown determinista bidireccional podría simularse en tiempo lineal y extrajo una versión temprana de "KMP" especializándose la simulación a un autómata de coincidencia de cuerdas. Pratt contribuyó con una mejora de la eficiencia. Ver Knuth's retelling.
Estoy desconcertado por votos cerrados. Estoy realmente confundido acerca de qué preguntar y qué no. – anonymous
Algunas personas votan para cerrar preguntas que no tienen "contenido de programación", sea lo que sea lo que signifique eso. – Per