A string-matching algorithm that searches for a pattern within a text in linear time by precomputing, from the pattern alone, how far to skip ahead after a partial match fails, avoiding the need to re-examine text already matched.
Facts
Origin YearThe algorithm was conceived by James H. Morris and independently discovered by Donald Knuth soon after; Morris and Vaughan Pratt circulated a technical report on it in 1970, and all three published it jointly in 1977. Core PrincipleA string-searching algorithm that, on a mismatch, uses information already gathered about the pattern itself to skip ahead in the search rather than re-examining characters already matched, giving linear-time string matching. 1 Connections
In Field
Invented
Donald Knuth co-developed the linear-time string search algorithm with Vaughan Pratt and James H. Morris, published in 1977.
Sources
1. Wikipedia: Knuth-Morris-Pratt algorithm
Wikimedia FoundationLead section, history sentence
The three also published the algorithm jointly in 1977.
Lead section, first paragraph
when a mismatch occurs, the word itself embodies sufficient information to determine where the next match could begin, thus bypassing re-examination of previously matched characters.
View the Source Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.