Knuth-Morris-Pratt algorithm

From Wiktionary, the free dictionary
Jump to navigation Jump to search

English

[edit]

Etymology

[edit]

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

Proper noun

[edit]

the Knuth-Morris-Pratt algorithm

  1. (computing theory) 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.