Knuth–Morris–Pratt algorithm: Difference between revisions

Revision as of 13:10, 20 February 2005

Revision as of 01:53, 12 March 2005

Line 3:

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

==The KMP Algorithmalgorithm==

To motivate the technical details, we consider a specific instance. In this article, we will be using [[Array#Indices into Arrays|zero-based arrays]] for our strings; thus the 'C' in <math>P</math> will be denoted <math>P[2]</math>. Let <math>m</math> be the start of the currently matched substring within <math>S</math> and <math>i</math> the position within <math>P</math>.