Knuth–Morris–Pratt algorithm
Algoritmo Knuth-Morris-Pratt
- Date
- 1970 · confidence high
- Place
- Stanford, California, United States
- Credited to
- James H. Morris, Donald Knuth and Vaughan Pratt
- Field
- Knowledge & symbols
What it is
A substring-search algorithm that, on a mismatch, uses information already gathered from the search word itself to avoid re-examining characters, producing the first linear-time string-matching algorithm.
Conceived by Morris and independently discovered by Knuth; the three published it together in 1977. Independently, Matiyasevich had found a similar algorithm in 1969.
What it led to
- Efficient text search in editors and databases
- Basis for later pattern-matching algorithms