In this lesson, we will implement the Knuth-Morris-Pratt (KMP) algorithm discussed in the previous article.
To recap, we use the KMP algorithm to find patterns in a given string, much faster than a typical brute-force approach. You might also remember that the prefix function lies at the heart of the KMP algorithm. In fact, the ideas involved in computing the prefix function are so central to the KMP algorithm that their corresponding implementations are strikingly similar!
If we showed you the elegant implementations of the KMP algorithm and the prefix function right now, the whole thing would almost seem to work like magic! However, all magic in programming arises from bits and pieces of code working together in a logical and inter-related fashion. Together, we will demystify them both by uncovering the inner workings, but it will also require grappling with some non-trivial ideas.
We hope you will have an intuitive grasp of what is going on behind the scenes by the end of this lesson.
On that note, here is an overview of what we will be covering in the following exercises to implement the Knuth-Morris-Pratt Algorithm:
- Revisiting the simplest way to find a pattern in a text using a brute-force algorithm.
- Improving over the brute-force algorithm by noticing that we can use information about the pattern.
- Accomplishing this goal by computing the prefix function for the pattern.
- Identifying some clever manipulations to reduce the running time of computing the prefix function.
- Using the pre-computed values in the prefix function to perform faster pattern-matching - the Knuth-Morris-Pratt Algorithm!
Let’s get started!
In the code editor to the right, click Run to compare pattern searching with the KMP algorithm vs. a brute force algorithm. Which one runs faster in both instances? When does brute force run slowest?