Pattern Matching (KMP)
Scenario
You are writing a Network Intrusion Detection System that must find a 100-character malware signature hidden within a streaming 10-Terabyte network payload.
If you use a brute-force search and hit a mismatch on the 99th character, rewinding the search forces you to reread terabytes of data. How do you find the pattern without ever stepping backward?
Why it exists
Problem: The brute-force sliding window search resets the main text pointer backward every time a mismatch occurs. This redundant rescanning degrades performance to a catastrophic O(N * M) time complexity.
Naive approach: Align the pattern, check sequentially. On mismatch, move the pattern forward exactly 1 space, reset the pointers, and start checking from the beginning again.
Better idea: The Knuth-Morris-Pratt (KMP) algorithm precomputes the internal repetitions of the pattern. On a mismatch, it uses a state table to mathematically determine the maximum safe distance to shift the pattern forward, ensuring the main text pointer never moves backward.
Mental model
Imagine sliding a puzzle piece over a board. If the first half fits but the second half doesn't, you don't start over from millimeter one. You look at the ridges you already matched and slide the piece to the next logical ridge that could possibly fit.
KMP is a state machine. It builds a 'Failure Table' (LPS Array - Longest Proper Prefix which is also Suffix). When a mismatch happens, the table tells the algorithm: 'You successfully matched X characters. Based on internal repetitions, shift the pattern index to Y, but keep the main text pointer exactly where it is.'
Repeated decision: If characters match: advance both pointers. If they mismatch: look up the fallback index in the LPS array and shift the pattern pointer. The text pointer NEVER decrements.
Explanation
KMP has two phases.
1. Preprocessing (O(M)): It analyzes the pattern string to find internal repetitions, building the LPS array. If the pattern is 'ABABC', the array tracks that 'AB' repeats. The LPS value at a given index j indicates the length of the longest proper prefix that matches a suffix ending at j.
2. Search (O(N)): It traverses the main text. Let's say we matched 'ABAB' but failed on 'C'. A brute-force search shifts the pattern forward by 1 and restarts. KMP consults the LPS array for 'ABAB'. It realizes, 'Wait, a suffix of ABAB is AB, which is also the prefix of the pattern!'
Instead of restarting, KMP slides the pattern forward so that the prefix 'AB' aligns with the already-scanned suffix 'AB' in the text. The main text pointer doesn't move. We instantly resume checking the next character. This guarantees an O(N) linear scan.
Key points
- O(N + M) Time: Preprocessing takes O(M) where M is pattern length. Searching takes O(N). It is strictly linear.
- Zero Backtracking: The primary pointer traversing the massive text string is strictly monotonically increasing. It never decrements.
- The LPS Array: The Longest Proper Prefix which is also Suffix array acts as a deterministic state machine telling the algorithm how to recover from failure.
Pattern: State Machine / Redundancy Elimination
Recognition cues:
- The problem asks you to implement `strStr()` or find the first occurrence of a substring.
- The text dataset is described as a 'stream' that cannot be rewound or buffered in memory.
Failure signals
- You have nested loops where the outer loop iterates `i` through the text, and the inner loop iterates `j` through the pattern, and a failure breaks the inner loop (this is O(N*M)).
Engineering examples
Genomic Sequence Alignment
Finding specific gene markers in billions of DNA base pairs.
Genomic data has massive repeating sequences (e.g., GATTACA). Brute-force degrades instantly. KMP jumps repetitive mismatches optimally.
Network Packet Sniffing
Detecting malware signatures in real-time streaming traffic.
Because KMP never backtracks the main pointer, it can process infinite streams of data byte-by-byte as they arrive on the network card.
When not to use
- You need to search for hundreds of patterns simultaneously: KMP is for a single pattern. For searching multiple keywords concurrently (like a censor filter), algorithms like Aho-Corasick are required.
Common mistakes
- Over-engineering simple tasks: In production, language built-ins like `.indexOf()` or `.find()` are heavily optimized at the C/Assembly level and are almost always faster for normal-sized strings than manually writing KMP in a high-level language.
- Misunderstanding the 'Proper Prefix': The LPS array strictly requires a *proper* prefix—one that is strictly shorter than the full string being evaluated. The full string cannot be its own prefix in this calculation.
Glossary
- internal repetitions
- Patterns within a string that repeat themselves, like a suffix that is identical to a prefix.
- state machine
- A system that moves between different conditions or stages based on specific rules and inputs.
- monotonically increasing
- Constantly moving forward without ever going backwards.
Recall questions
- What fatal flaw in the brute-force substring search does KMP fix?
- What is the purpose of the LPS array in KMP?
- What is the total time complexity of KMP?
Questions & answers
Implement strStr(): Find the index of the first occurrence of `needle` in `haystack` in O(N) time.
Precompute the LPS array for the `needle` in O(M) time. Traverse the `haystack`. On mismatch, update the needle pointer using the LPS array without decrementing the haystack pointer.
Approach: Knuth-Morris-Pratt Algorithm.
Find the shortest string that contains the given string as a repeating substring.
Compute the LPS array of the string. The length of the shortest repeating substring is `N - LPS[N-1]`. If `N % (N - LPS[N-1]) == 0`, it is a valid repeating substring.
Approach: LPS array properties.
Interesting facts
- KMP was conceived independently in 1969 by Matiyasevich (via Turing machine research) and later formalized by Knuth, Morris, and Pratt in 1970.
Continue learning
Previous: String Traversal
Related: String Traversal