Knuth–Morris–Pratt algorithm: Difference between revisions

Revision as of 11:03, 15 September 2021

Revision as of 12:35, 15 September 2021

Line 1:

{{Short description|Algorithm for finding sub-text ___location(s) inside a given sentence in Big O(n) time}}<!--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=Θ<math>\Theta(m)</math> preprocessing + Θ<math>\Theta(n)</math> matching<ref group="note">''<math>m''</math> is the length of the pattern, which is the string we are searching for in the text which is of length ''<math>n''</math></ref>|space=Θ<math>\Theta(m)</math>}}

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.