Knuth–Morris–Pratt algorithm: Difference between revisions

Revision as of 15:59, 6 August 2020

Revision as of 22:54, 11 August 2020

Line 1:

<!--If you are thinking of adding an implementation of this algorithm in a particular language, think again. See the talk page.-->{{Infobox algorithm|name=Knuth–Morris–Pratt algorithm|data=[[String (computer science)|String]]|class=[[String-searching algorithm|String search]]|time=Θ(m) preprocessing + Θ(n) matching<ref group="note">''m'' is the length of the pattern, which is the string we are searching for in the text which is of length ''n''</ref>|space=Θ(m)}}

In [[computer science]], the '''Knuth–Morris–Pratt [[string-searching algorithm]]''' (or '''KMP algorithm''') searches for occurrences of a "word" <code>W</code> within a main "text string" <code>S</code> by employing the observation that when a mismatch occurs, the word itself embodies sufficient information to determine where the next match could begin, thus bypassing re-examination of previously matched characters.

Line 421 ⟶ 422:

'''let''' T[pos] ← cnd

'''let''' cnd ← T[cnd] (to increase performance)

'''while''' cnd ≥ 0 '''and''' W[pos] <>≠ W[cnd] '''do'''

'''let''' cnd ← T[cnd]

'''let''' pos ← pos + 1, cnd ← cnd + 1