Knuth–Morris–Pratt algorithm
In computer science, the Knuth–Morris–Pratt string-searching algorithm (or KMP algorithm) searches for occurrences of a "word" W within a main "text string" S 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.
- Class
- String-searching algorithm
- Comment
- enIn computer science, the Knuth–Morris–Pratt string-searching algorithm (or KMP algorithm) searches for occurrences of a "word" W within a main "text string" S 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.
- Data
- String (computer science)
- Has abstract
- enIn computer science, the Knuth–Morris–Pratt string-searching algorithm (or KMP algorithm) searches for occurrences of a "word" W within a main "text string" S 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 by James H. Morris and independently discovered by Donald Knuth "a few weeks later" from automata theory.Morris and Vaughan Pratt published a technical report in 1970.The three also published the algorithm jointly in 1977. Independently, in 1969, Matiyasevich discovered a similar algorithm, coded by a two-dimensional Turing machine, while studying a string-pattern-matching recognition problem over a binary alphabet. This was the first linear-time algorithm for string matching.
- Is primary topic of
- Knuth–Morris–Pratt algorithm
- Label
- enKnuth–Morris–Pratt algorithm
- Link from a Wikipage to an external page
- www.ics.uci.edu/~eppstein/161/960227.html
- www.ics.uci.edu/~eppstein/161/kmp/
- yurichev.com/news/20210121_Knuth_Morris_Pratt_1/
- yurichev.com/news/20210121_Knuth_Morris_Pratt_2/
- yurichev.com/news/20210121_Knuth_Morris_Pratt_3/
- archive.org/details/introductiontoal00corm_691
- toccata.lri.fr/gallery/kmp.en.html
- github.com/rvhuang/kmp-algorithm
- www.w3spot.com/2020/07/kmp-algorithm-explained-in-plain-english.html
- www.inf.fh-flensburg.de/lang/algorithmen/pattern/kmpen.htm
- web.archive.org/web/20101227102334/http:/oak.cs.ucla.edu/cs144/examples/KMPSearch.html
- archive.org/details/introductiontoal00corm_691/page/n945
- www-igm.univ-mlv.fr/~lecroq/string/node8.html
- www.avhohlov.narod.ru/p2250en.htm
- www.cs.pitt.edu/~kirk/cs1501/animations/String.html
- www.youtube.com/watch%3Fv=4jY57Ehc14Y
- www.youtube.com/watch%3Fv=Zj_er99KMb8
- Link from a Wikipage to another Wikipage
- Algorithm
- Automata theory
- Big O notation
- Big-O notation
- Brute-force search
- Category:1970 in computing
- Category:Articles with example pseudocode
- Category:Donald Knuth
- Category:String matching algorithms
- Computational complexity theory
- Computer science
- David Eppstein
- Donald Knuth
- James H. Morris
- Lexicographically minimal string rotation
- Linear time
- Pseudocode
- Real-time computing
- String (computer science)
- String-searching algorithm
- Substring
- Vaughan Pratt
- Yuri Matiyasevich
- Name
- enKnuth–Morris–Pratt algorithm
- SameAs
- 4CBds
- Algorithme de Knuth-Morris-Pratt
- Algoritma Knuth-Morris-Pratt
- Algoritmo de Knuth-Morris-Pratt
- Algoritmo di Knuth-Morris-Pratt
- Algoritmo Knuth-Morris-Pratt
- Algorytm Knutha-Morrisa-Pratta
- KMP算法
- Knuth-Morris-Pratt-Algorithmus
- m.01lksg
- Q45285
- Thuật toán Knuth–Morris–Pratt
- Алгоритм Кнута — Морриса — Пратта
- Алгоритм Кнута — Морріса — Пратта
- Кнут-Морис-Прат алгоритам
- Кнут-Моррис-Пратт алгоритмі
- אלגוריתם KMP
- الگوریتم تطابق رشته با زمان خطی
- ขั้นตอนวิธีของคนูธ-มอร์ริส-แพรตต์
- クヌース–モリス–プラット法
- 커누스-모리스-프랫 알고리즘
- Subject
- Category:1970 in computing
- Category:Articles with example pseudocode
- Category:Donald Knuth
- Category:String matching algorithms
- Time
- enpreprocessing + matching
- WasDerivedFrom
- Knuth–Morris–Pratt algorithm?oldid=1116828644&ns=0
- WikiPageLength
- 33839
- Wikipage page ID
- 253227
- Wikipage revision ID
- 1116828644
- WikiPageUsesTemplate
- Template:Citation needed
- Template:Cite book
- Template:Color
- Template:Donald Knuth navbox
- Template:Infobox algorithm
- Template:Reflist
- Template:Short description
- Template:Strings
- Template:Wikibooks