Initialize pointers and prefix table
Data / Knowledge library
Knuth-Morris-Pratt Algorithm
Uses a prefix table to avoid rechecking text after a pattern mismatch
Why learn Knuth-Morris-Pratt Algorithm?
It guarantees linear-time exact substring search
The problem it solves
It finds pattern occurrences without backing up through already matched input
Where it came from
Knuth-Morris-Pratt Algorithm is a algorithm that uses a prefix table to avoid rechecking text after a pattern mismatch. Its guarantees and tradeoffs depend on the concrete implementation and operating context.
Build your understanding
Work through these exercises in order. Try the task before opening a reference.
- Define Knuth-Morris-Pratt Algorithm and distinguish it from a neighboring concept.
- Choose a realistic task where Knuth-Morris-Pratt Algorithm is appropriate.
- Identify a failure mode caused by misusing Knuth-Morris-Pratt Algorithm.
- Interpret a small design or result involving Knuth-Morris-Pratt Algorithm.
- Explain one tradeoff or limitation of Knuth-Morris-Pratt Algorithm.
Documentation and sources
- NIST Dictionary of Algorithms and Data Structures (xlinux.nist.gov)
Connect the ideas
Explore next
Real World Example
High-Throughput Log Pattern Analysis
Cybersecurity operations centers monitoring massive server log streams.
The business problem
Brute-force string searching causes significant latency when scanning multi-gigabyte log files for specific threat signatures, as it repeatedly re-scans characters after partial matches.
How this topic solves it
The Knuth-Morris-Pratt (KMP) algorithm uses a prefix table to store information about the pattern's internal structure, allowing the search to skip redundant comparisons and avoid rechecking text after a pattern mismatch.
- Preprocess the target pattern to build a prefix table (failure function) that identifies the longest proper prefix that is also a suffix.
- Initialize a pointer for the text and a pointer for the pattern.
- Compare characters at the current pointers.
- If a mismatch occurs, use the prefix table to shift the pattern pointer to the next viable position without backtracking the text pointer.
- Continue until the pattern is found or the text is exhausted.
This diagram illustrates how the algorithm transitions between states based on character matching or mismatching.
Check text[i] against pattern[j]
Consult prefix table to update j
Increment i and j
Pattern located in text
- Start → Begin → Compare
- Compare → Match → Match
- Compare → Mismatch → Mismatch
- Mismatch → Shift pattern → Compare
- Match → j == pattern length → Found
Expected business outcome
Improved search efficiency in large datasets by ensuring each character in the text is processed a constant number of times, regardless of the number of partial matches.
Limitations and checks
The algorithm requires additional memory proportional to the length of the pattern to store the prefix table, which can be a constraint in extremely memory-limited embedded systems.