Algoritmo Knuth-Morris-Pratt
Knuth–Morris–Pratt algorithm
- Fecha
- 1970 · fiabilidad alta
- Lugar
- Stanford, California, Estados Unidos
- Autoría
- James H. Morris, Donald Knuth y Vaughan Pratt
- Ámbito
- Saber y símbolos
Qué es
Algoritmo de búsqueda de subcadenas que, al detectar un fallo de coincidencia, usa la información ya obtenida de la propia palabra buscada para no reexaminar caracteres, logrando el primer algoritmo de búsqueda de texto en tiempo lineal.
Concebido por Morris y descubierto independientemente por Knuth; los tres lo publicaron juntos en 1977. De forma independiente, Matiyasévich había hallado un algoritmo similar en 1969.
A qué dio paso
- Búsqueda de texto eficiente en editores y bases de datos
- Base de algoritmos posteriores de coincidencia de patrones