Knuth–Morris–Pratt algorithm: Difference between revisions

Revision as of 22:44, 30 July 2004

Revision as of 09:52, 13 September 2004

Line 53:

|}

This is the precomputed table of offsets generated by the algorithm. If we look at the table, we can see that these numbers are the maximum number of characters matchable before the ''n''th position on the string (without matching the entire prefix of ''n'' characters).

For example take position 6

Line 61:

^

The pointer is at position 6. As you can seeseen above, the maximum number of characters that can matched before position 6 is 2. TheThus, the array entry of 6 is 2.

===Processing text===