En informática , el algoritmo de búsqueda de cadenas Knuth-Morris-Pratt (o algoritmo KMP ) busca ocurrencias de una "palabra" Wdentro de una "cadena de texto" principal Sempleando la observación de que cuando ocurre una falta de coincidencia, la palabra en sí misma contiene suficiente información. para determinar dónde podría comenzar la próxima coincidencia, evitando así volver a examinar los caracteres previamente coincidentes.
El algoritmo fue concebido por James H. Morris y descubierto de forma independiente por Donald Knuth "unas semanas después" a partir de la teoría de los autómatas . [1] [2] Morris y Vaughan Pratt publicaron un informe técnico en 1970. [3] Los tres también publicaron el algoritmo conjuntamente en 1977. [1] Independientemente, en 1969, Matiyasevich [4] [5] descubrió un algoritmo similar, codificado por una máquina de Turing bidimensional, mientras estudiaba un problema de reconocimiento de coincidencia de patrones de cuerdas sobre un alfabeto binario. Este fue el primer algoritmo de tiempo lineal para la coincidencia de cadenas. [6]
Un algoritmo de coincidencia de cadenas desea encontrar el índice inicial men una cadena S[]que coincida con la palabra de búsqueda W[].
El algoritmo más sencillo, conocido como algoritmo de " fuerza bruta " o "ingenuo", consiste en buscar una coincidencia de palabra en cada índice m, es decir, la posición en la cadena que se busca que corresponde al carácter S[m]. En cada posición m, el algoritmo primero comprueba la igualdad del primer carácter de la palabra que se busca, es decir, S[m] =? W[0]. Si se encuentra una coincidencia, el algoritmo prueba los otros caracteres de la palabra que se busca comprobando los valores sucesivos del índice de posición de la palabra, i. El algoritmo recupera el carácter W[i]de la palabra buscada y comprueba la igualdad de la expresión S[m+i] =? W[i]. Si todos los caracteres sucesivos coinciden en Wla posiciónm, entonces se encuentra una coincidencia en esa posición en la cadena de búsqueda. Si el índice mllega al final de la cadena, entonces no hay coincidencia, en cuyo caso se dice que la búsqueda "falla".
Por lo general, la verificación de prueba rechazará rápidamente la coincidencia de prueba. Si las cadenas son letras aleatorias distribuidas uniformemente, entonces la posibilidad de que los caracteres coincidan es de 1 en 26. En la mayoría de los casos, la verificación de prueba rechazará la coincidencia en la letra inicial. La posibilidad de que las dos primeras letras coincidan es de 1 en 26 2 (1 en 676). Entonces, si los caracteres son aleatorios, entonces la complejidad esperada de buscar una cadena S[]de longitud n es del orden de n comparaciones u O ( n ). El rendimiento esperado es muy bueno. Si S[]tiene 1 millón de caracteres y W[]tiene 1000 caracteres, entonces la búsqueda de cadenas debe completarse después de aproximadamente 1,04 millones de comparaciones de caracteres.
Ese rendimiento esperado no está garantizado. Si las cadenas no son aleatorias, la verificación de una prueba mpuede requerir muchas comparaciones de caracteres. El peor de los casos es si las dos cadenas coinciden en todas menos en la última letra. Imagine que la cadena S[]consta de 1 millón de caracteres que son todos A y que la palabra W[]tiene 999 caracteres A que terminan en un carácter B final . El algoritmo simple de coincidencia de cadenas ahora examinará 1000 caracteres en cada posición de prueba antes de rechazar la coincidencia y avanzar la posición de prueba. El ejemplo de búsqueda de cadena simple ahora requeriría alrededor de 1000 comparaciones de caracteres por 1 millón de posiciones para 1000 millones de comparaciones de caracteres. Si la longitud de W[]es k, entonces el desempeño en el peor de los casos es O ( k ⋅ n ).