Word.ws English Dictionary

Knuth-Morris-Pratt algorithm

Knuth-Morris-Pratt algorithm proper noun: a linear-time algorithm that searches for occurrences of one text string within another, employing the observation that when a mismatch occurs, the search string itself embodies sufficient information to determine where the next match could begin, thus reducing the number of possible match locations that must be checked.

Proper noun

the Knuth-Morris-Pratt algorithm

  1. A linear-time algorithm that searches for occurrences of one text string within another, employing the observation that when a mismatch occurs, the search string itself embodies sufficient information to determine where the next match could begin, thus reducing the number of possible match locations that must be checked.

Origin of Knuth-Morris-Pratt algorithm

The algorithm was conceived in 1970 by Donald Knuth and Vaughan Pratt, and independently by James H. Morris.

Questions about Knuth-Morris-Pratt algorithm

What does Knuth-Morris-Pratt algorithm mean?
Knuth-Morris-Pratt algorithm means a linear-time algorithm that searches for occurrences of one text string within another, employing the observation that when a mismatch occurs, the search string itself embodies sufficient information to determine where the next match could begin, thus reducing the number of possible match locations that must be checked.
What part of speech is Knuth-Morris-Pratt algorithm?
Knuth-Morris-Pratt algorithm is a proper noun.

Words near Knuth-Morris-Pratt algorithm in the dictionary

  1. knut
  2. Knute
  3. Knuth
  4. Knuth equivalence
  5. Knuth-Bendix completion algorithm
  6. Knuth-Morris-Pratt algorithm
  7. Knuthian
  8. Knuths
  9. knuts
  10. Knutsford
  11. Knutson

Source and license

Adapted from Wiktionary: Knuth-Morris-Pratt algorithm (page history and authors). Text available under the Creative Commons Attribution-ShareAlike 4.0 license. Word.ws reformatted the entry and added links. Wiktionary data of 2026-09-02.

Last updated:

Cite this entry: “Knuth-Morris-Pratt algorithm.” Word.ws, https://word.ws/knuth-morris-pratt_algorithm. Based on Wiktionary, CC BY-SA 4.0.