Knuth–Morris–Pratt algorithm: Difference between revisions

Revision as of 01:59, 22 November 2005

Revision as of 07:21, 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 [[1977]], but the three published it jointly.

==The KMP algorithm==

Line 182:

==References==

* [[Donald Knuth]], [[James Morris]], and [[Vaughan Pratt]]. Fast pattern matching in strings. ''SIAM Journal on Computing'', 6(2):323&ndash;350. 1977. [http://citeseer.ist.psu.edu/context/23820/0 Citations]. Original publication.

* [[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ronald L. Rivest]], and [[Clifford Stein]]. ''[[Introduction to Algorithms]]'', Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0262032937. Section 32.4: The Knuth-Morris-Pratt algorithm, pp.923&ndash;931.