Overview
5 Knuth-Morris-Pratt Algorithm
Knuth-Morris-Pratt is presented as a smarter alternative to naive string searching, one that avoids the costly backtracking that makes simple pattern matching slow on repetitive inputs. Instead of treating a mismatch as a dead end, the algorithm uses the information gained from already matched characters to continue searching without rechecking the text from the beginning. This shift in thinking is the key idea behind its efficiency and is what separates it from hash-based methods like Rabin-Karp.
The chapter explains that KMP works in two stages: first, it preprocesses the pattern to build the LPS array, which records the longest proper prefix that is also a suffix for each position in the pattern. This array can be constructed in linear time, O(m), and serves as a lookup table for how far the pattern can shift after a mismatch. During the actual search, two pointers move through the text and pattern, but the text pointer never moves backward, which guarantees a linear scan of the text and overall O(n + m) time.
Through worked examples, the text shows how the LPS array is built and then used to skip redundant comparisons while matching patterns in longer texts. It also emphasizes practical uses such as log analysis, real-time streaming, and intrusion detection systems, where forward-only scanning is especially valuable. At the same time, it notes the trade-off: KMP requires extra preprocessing time and memory, and if the pattern has little or no repetition, the benefit can disappear and the method may offer little advantage over simpler approaches.
To create the LPS array, we start with an empty array of the same length as that of the pattern. We initialize a variable length as 0, and an iterator i starts with 1, which will track the current character.
The KMP match starts with two pointers, i and j, starting at 0. If it’s a match with text and pattern, we increment i and j by 1 and so on. At index 6, enclosed with a box there is a mismatch of character ‘e’ with ‘c’
The pattern shifts to the right, and the comparison now takes place with ‘e’ and ‘a’. A mismatch occurs again, but the value of j is already at 0, looking at the LPS array. So now i is incremented by 1 to 6.
The text and the pattern match perfectly till i = 3. At i = 3, the character is ‘x’ and j = 3 is ‘d’, a mismatch occurs. In the LPS array, we look at the previous LPS[j-1] and set that value to j. The right shift of the pattern can be calculated as j - LPS[j-1], which is 3 - 0 spaces towards the right.
The shift by 3 characters is completed. Now i = 3 and j = 0, a mismatch occurs, but j is already 0, so increment i by 1, and j is still 0. The next comparison is with i = 4 and j = 0, which is a match. Proceeding further, i increments until 10 and j increments until 6, a mismatch between ‘x’ and ‘c’ occurs. Previous LPS[6-1] is set to j. The visual shift is going to be j - LPS[j-1], which is 6 -2 = 4 spaces towards the right.
A comparison is done with ‘x’ and 'c', which is a mismatch. Since, LPS[1] is 0, we increment i by 1. The pointer i = 11 and j = 0. The pointer i increases up to 18 for character ‘d’, and pointer j increments till 7 for character ‘y’. Mismatch occurs here, and LPS[7-1] = 3 is set to the pointer j. Ths shift is 7 - 3 = 4 spaces towards the right.
This is the final check where the full match occurs. We have moved 4 spaces towards the right, matching the pointer and j = 3. The sequence a b c is already compared, and pointer i = 18 with j = 3, so the comparison starts again. The comparison ends with all characters of the text matched with the pattern. The pattern is found from pointer i = 15 to 22 in the text.
Summary
- The Knuth-Morris-Pratt Algorithm (KMP) introduces the concept where a mismatch is not a failure but a source of information. Naive and brute force algorithms reset the text pointer to the start when a mismatch occurs
- The time complexity without KMP is O(nm), where n is the length of the text and m is the length of the pattern.
- KMP makes sure the text pointer only moves forward in linear time.
- The search pattern is preprocessed and stored in auxiliary space called the Longest Prefix which is also the Suffix (LPS) array. This operation is done in O(m) time.
- For every index in the pattern, the LPS array calculates the length of the longest contiguous sequence of characters at the beginning of the string that perfectly matches the sequence at the end.
- During a mismatch at pattern index j, the algorithm avoids a full reset. It consults the LPS array (LPS[j-1]) to determine exactly how many characters of the prefix are guaranteed to still match the text. This makes it deterministic.
- The physical distance the pattern slides to the right during a mismatch is mathematically defined by, j - LPS[j-1]
- By decoupling the pattern analysis from the text scanning, the actual search phase executes in strictly O(n) time, bringing the total algorithmic time complexity to O(n + m).
- KMP is the foundational algorithm for continuous, real-time data streaming, live log analysis, and line-speed network Intrusion Detection Systems (IDS).
- KMP derives its power exclusively from pattern repetition. If there is no repetition in the pattern or the text, the LPS array is not useful, and the approach falls to the naive approach with worse time complexity. This is because the LPS array without repetition consists of only zeroes. Every mismatch reset the pointer to 0, making it naive.
- The original paper of this algorithm is https://www.cs.jhu.edu/~misha/Spring23/Knuth77.pdf.
- Practice Problems of string matching specifically for bioinformatics here - https://rosalind.info/problems/list-view/
- YouTube video - https://www.youtube.com/playlist?list=PL_drzcX_ki75Hif00uAhycjlqDNi0ZVlC
Algorithms Every Programmer Should Know ebook for free
