5 Knuth-Morris-Pratt Algorithm
This chapter covers
- Critiquing the computational bottleneck of backtracking in naive string searches
- Constructing the LPS (Longest Prefix Suffix) array in O(m) time
- Executing the deterministic two-pointer shift formula to achieve strictly O(n)
- Learning real-world application, memory overhead for real-time data streaming
Previously, we used the Rabin-Karp algorithm to match patterns or substring within long texts. It uses a hash function as its core approach in finding the pattern. Creating hash functions and making sure to minimize the collisions. This chapter covers another way of finding patterns and substrings in text without the hash function.
In 1977, the foundational string-matching algorithm was formally proposed by Donald E. Knuth, James H. Morris, and Vaughan R. Pratt in their paper, “Fast Pattern Matching in Strings.” It is widely recognized as the Knuth-Morris-Pratt string matching algorithm, or KMP algorithm.
Before KMP, standard string search methods were fundamentally inefficient due to backtracking. The naive approach is to use two pointers and start comparing the characters of the text and the pattern. At any given point in time, there is a mismatch, the pointer resets and starts checking the pattern again. This led to a significant performance bottleneck, particularly when searching highly repetitive texts.