Knuth–Morris–Pratt algorithm: Difference between revisions

Revision as of 18:54, 5 February 2005

Revision as of 10:50, 6 February 2005

Line 12:

i: 0123456

We begin bya matchingstep theby firstmatching threeeach characterscharacter one after another. Thus in the fourth step, <math>m = 0</math> and <math>i = 3</math>. But <math>S[3]</math> is a space and <math>P[3] = 'D'</math>, so we have a mismatch. Rather than beginning again at <math>m = 1</math>, we note that no 'A' occurs between positions 0 and 3 in <math>P</math> except at 0; hence, having checked all those characters previously, we know there is no chance of finding the beginning of a match if we check them again. Therefore we move on to the next character, setting <math>m = 4</math> and <math>i = 0</math>.

m: 01234567890123456789012