algoritmo Knuth-Morris-Pratt

El algoritmo KMP es un algoritmo de búsqueda de subcadenas simple. Por lo tanto su objetivo es buscar la existencia de una subcadena (habitualmente llamada patrón) dentro de otra cadena. La búsqueda se lleva a cabo utilizando información basada en los fallos previos. Información obtenida del propio patrón creando previamente una tabla de valores sobre su propio contenido. El objetivo de crear dicha tabla es poder determinar donde podría darse la siguiente existencia, sin necesidad de analizar más de 1 vez los caracteres de la cadena donde se busca. En 1970 S.A. Cook sugirió la existencia de un algoritmo que resuelve la búsqueda en un tiempo equivalente a M+N, en el peor caso, a raíz de unos resultados teóricos que obtuvo mientras probaba un tipo de máquina abstracta.​ Knuth y Pratt siguiendo los pasos que Cook usó para probar su teorema, lograron crear el algoritmo que lleva sus nombres. De modo independiente mientras trabajaba en un editor de texto acabó descubriendo el mismo algoritmo, para satisfacer la cuestión de la búsqueda eficiente de subcadenas, y que publicaron juntos los tres en 1976.