Revision as of 10:25, 15 April 2018 edit Rahul bhanushali (talk \| contribs) 4 edits Added the content about how this algorithm works and compare with naive string matching algorithm Tags: Visual edit Mobile edit Mobile web edit ← Previous edit		Revision as of 09:29, 17 April 2018 edit undo 146.52.178.193 (talk) Remove grammatically incorrect sentence that didn't add valuable information (and wasn't sourced) anyway Next edit →
Line 4: 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. The [[algorithm]] was conceived in 1970 by [[Donald Knuth]] and [[Vaughan Pratt]], and independently by [[James H. Morris]].This is the first linear time algorithm for string matching. ~~It utilizes the concept of naive approach in some different way.~~ The three published it jointly in 1977.<ref>{{cite journal\|last1=Knuth\|first1=Donald\|last2=Morris\|first2=James H.\|last3=Pratt\|first3=Vaughan\|title=Fast pattern matching in strings\|journal=SIAM Journal on Computing\|date=1977\|volume=6\|issue=2\|pages=323–350\|doi=10.1137/0206024\|url=http://epubs.siam.org/doi/abs/10.1137/0206024}}</ref> Independently, in 1969, [[Yuri Matiyasevich\|Matiyasevich]]<ref>{{cite journal \| language = ru \| last1 = Матиясевич

Knuth–Morris–Pratt algorithm: Difference between revisions