Knuth–Morris–Pratt algorithm: Difference between revisions

Revision as of 16:18, 4 February 2005

Revision as of 16:20, 4 February 2005

Line 25:

# Compare <math>P[i]</math> versus <math>S[j]</math>. At this point we have already matched <math>i</math> previous characters.

#* If they are equal, set <math>i = i + 1</math>, <math>j = j + 1</math>. If <math>i = n</math> then we have found a full match; terminate the algorithm and return <math>m</math> as the start of the match.

#* If they are unequal, let <math>e = T[i - 1]</math> be an entry in the "partial match" table described below, at position <math>i - 1</math>. Set <math>m = j - e</math>, and <math>i = e</math> if <math>e \geqslantneq 0-1</math>, or <math>m = j + 1</math>, <math>j = j + 1</math>, and <math>i = 0</math> if <math>e = -1</math>.

# Return to step 2.