Knuth–Morris–Pratt algorithm
E94984
The Knuth–Morris–Pratt algorithm is a classic linear-time string-searching algorithm that efficiently finds occurrences of a pattern within a text by precomputing a prefix function to avoid redundant comparisons.
Aliases (1)
Statements (50)
| Predicate | Object |
|---|---|
| instanceOf |
deterministic algorithm
→
linear-time algorithm → pattern-matching algorithm → string-search algorithm → |
| application |
pattern matching in compilers
→
search in DNA or protein sequences → search in network intrusion detection systems → text editors search functionality → |
| authorsOfOriginalPaper |
Donald E. Knuth
NERFINISHED
→
James H. Morris Jr. NERFINISHED → Vaughan R. Pratt NERFINISHED → |
| avoids |
backtracking in the text
→
re-examining characters in the text → |
| category |
exact string matching algorithms
→
|
| comparedWith |
Boyer–Moore algorithm
→
Rabin–Karp algorithm NERFINISHED → naive string-search algorithm → |
| describedIn |
"Fast Pattern Matching in Strings"
→
|
| field |
algorithms
→
computer science → stringology → |
| hasPhase |
preprocessing phase
→
search phase → |
| input |
pattern string
→
text string → |
| introducedIn |
1977
→
|
| keyIdea |
avoid redundant comparisons by reusing previous match information
→
precompute longest proper prefix which is also suffix for each pattern position → |
| namedAfter |
Donald Knuth
NERFINISHED
→
James H. Morris NERFINISHED → Vaughan Pratt → |
| output |
starting indices of pattern occurrences in text
→
|
| preprocessingPhaseComplexity |
O(m)
→
|
| property |
guaranteed worst-case linear time
→
runs in time linear in the length of the text plus pattern → stable performance independent of alphabet size → |
| purpose |
find occurrences of a pattern in a text
→
|
| searchPhaseComplexity |
O(n)
→
|
| spaceComplexity |
O(m)
→
|
| taughtIn |
data structures and algorithms curricula
→
undergraduate algorithms courses → |
| timeComplexity |
O(n + m)
→
|
| timeComplexityBestCase |
O(n)
→
|
| timeComplexityWorstCase |
O(n + m)
→
|
| typicalRepresentation |
pseudocode in algorithm textbooks
→
|
| usesConcept |
border of a string
→
failure function → prefix function → proper prefix → proper suffix → |
Referenced by (2)
| Subject (surface form when different) | Predicate |
|---|---|
|
Knuth–Morris–Pratt algorithm
(""Fast Pattern Matching in Strings"")
→
|
describedIn |
|
Donald E. Knuth
→
|
knownFor |