Knuth–Morris–Pratt algorithm: Difference between revisions

Content deleted Content added
thus is confusing. the space complexity W is not that because of the time complexity being W it is that because the array is size W
No edit summary
Tags: Mobile edit Mobile app edit Android app edit
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=Θ(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.