Knuth–Morris–Pratt algorithm
Algorithm for finding sub-text location(s) inside a given sentence in Big O(n) time / From Wikipedia, the free encyclopedia
Dear Wikiwand AI, let's keep it short by simply answering these key questions:
Can you list the top facts and stats about Knuth–Morris–Pratt algorithm?
Summarize this article for a 10 year old
In computer science, the Knuth–Morris–Pratt algorithm (or KMP algorithm) is a string-searching algorithm that searches for occurrences of a "word" W
within a main "text string" S
by employing the observation that 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.
Class | String search |
---|---|
Data structure | String |
Worst-case performance | preprocessing + matching[note 1] |
Worst-case space complexity |
The algorithm was conceived by James H. Morris and independently discovered by Donald Knuth "a few weeks later" from automata theory.[1][2] Morris and Vaughan Pratt published a technical report in 1970.[3] The three also published the algorithm jointly in 1977.[1] Independently, in 1969, Matiyasevich[4][5] discovered a similar algorithm, coded by a two-dimensional Turing machine, while studying a string-pattern-matching recognition problem over a binary alphabet. This was the first linear-time algorithm for string matching.[6]