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.

Ask AI about this wordChatGPTClaudePerplexityGoogle AIGrok

Meanings

proper nounthe Knuth-Morris-Pratt algorithm
  1. computerA 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

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

Full word history & related roots →
Cite this entry
APA

Knuth-Morris-Pratt algorithm. (n.d.). In WatkinsX Dictionary. Retrieved November 3, 2026, from https://dictionary.watkinsx.com/word/Knuth-Morris-Pratt%20algorithm

MLA

“Knuth-Morris-Pratt algorithm.” WatkinsX Dictionary, https://dictionary.watkinsx.com/word/Knuth-Morris-Pratt%20algorithm. Accessed November 3, 2026.

Chicago

WatkinsX Dictionary, s.v. “Knuth-Morris-Pratt algorithm,” accessed November 3, 2026, https://dictionary.watkinsx.com/word/Knuth-Morris-Pratt%20algorithm.

Source: Knuth-Morris-Pratt algorithm on Wiktionary, CC BY-SA 4.0.