Knuth–Morris–Pratt algorithm: Difference between revisions

Revision as of 03:38, 19 November 2005

Revision as of 01:59, 22 November 2005

Line 2:

The '''Knuth-Morris-Pratt [[string searching algorithm]]''' searches for occurrences of a "pattern" string <math>P</math> within a main string <math>S</math> by employing the simple observation that when a mismatch occurs, we have enough knowledge simply by possessing the pattern to determine where the next match could begin, thus bypassing re-examination of previously matched characters.

The algorithm was invented by [[Donald Knuth|Knuth]] and [[Vaughan Pratt|Pratt]] and independently by [[J. H. Morris]] in [[19761977]].

==The KMP algorithm==