English Explanatory Dictionary

Knuth-Morris-Pratt algorithm

English dictionary entry

Meanings

name
  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.

Word forms

Knuth-Morris-Pratt algorithm the Knuth-Morris-Pratt algorithm

Etymology

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

This entry uses open data from Wiktionary (CC BY-SA/GFDL). Word forms are used for search and are not indexed as separate pages.
Back to search All on K Russian dictionary Dahl dictionary