Revision as of 03:20, 24 March 2004 edit Madoka (talk \| contribs) 230 edits Moved code example to discussion, for it may be incorrect. ← Previous edit		Revision as of 15:38, 13 May 2004 edit undo Jaredwf (talk \| contribs) 1,674 edits No edit summary Next edit →
Line 1: The '''Knuth-Morris-Pratt [[string searching algorithm]]''' locates a pattern of characters within a string. It uses the fact that after finding the first mismatch between pattern and string we already know the characters compared before to improve the efficiency of the search. We therefore will have to compare the pattern to itself to determine how many positions we have to move to the left. It was invented by [[Donald Knuth\|Knuth]] and [[Vaughan Pratt\|Pratt]] and independently by [[J. H. Morris]] in [[1976]].

Knuth–Morris–Pratt algorithm: Difference between revisions