Learn how to implement the Knuth-Morris-Pratt algorithm in Python!

Implementing the Knuth-Morris-Pratt Algorithm in Python

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!

Intro

Great job with getting `kmp_algorithm()` to work! Now we can come full circle and put it to the test against the same pattern and text that took `naive_pattern_matching()` a really long time to figure out back in Exercise two. 

Then, we will put it to the test against an even bigger input that took `rabin_karp_algorithm()` a really long time to run.




Rabin-Karp vs KMP

As we saw in the previous exercise, the brute-force algorithm to compute the prefix function requires double `for` loops resulting in a rather poor running time. However, it turns out that we can exploit the structure of a prefix function by employing some nifty tricks in order to speed up the computation of the same values!
 
An important step in optimizing algorithms is to make clever observations about the most crucial elements of the problem. And indeed, we start by asking - what can we say about the sequence of consecutive values of the prefix function?

```tex
\begin{array}{c}
\text{i}&0&1&2&3&4&5\\
 \text{pattern} & \color{blue} \text{A} & \color{blue} \text{B} & \color{blue} \text{A} & \color{blue} \text{B} & \color{blue} \text{A} & \color{blue} \text{C} \\
\text{pi[i]} & 0 & 0 & 1 & 2 & 3 & 0
\end {array}
```

You might have already noticed that each consecutive value can only increase at most by `1`. This is because each index is increasing by `1`, and so each corresponding length of a valid suffix can increase by no more than `1`.

What are the implications of this subtle observation? If the next value cannot increase by more than `1`, it means we are only left with three cases:

* The value can increase by `1`.
* The value can NOT increase at all i.e., stay the same.
* The value can actually decrease by a certain amount.

Let's handle these three cases separately and see how we can use this logic to speed up our code!


Computing the Prefix Function Faster - Part 1

Let's bring everything together to create the Knuth-Morris-Pratt algorithm!

The pseudocode for the KMP algorithm is extremely similar to that of the computation of the prefix function. In both cases, we are matching strings against each other using the same idea &mdash; the prefix function is a result of matching the pattern against itself, whereas the KMP algorithm uses the values of the prefix function to match the pattern against the text.

During the computation of the prefix function, we were interested in finding out whether the next character forms a new valid suffix. 

In the KMP algorithm, we are now interested in finding out the same for each character in the text. Whenever possible, we align a valid prefix of the pattern with its corresponding valid suffix in the text. This allows us to skip over characters we know cannot produce a match.

The pseudocode breakdown looks something like this:

* We start the algorithm by matching the pattern against the text character-by-character.
* If there is a mismatch, we look for a shorter valid prefix that can potentially align with an existing valid suffix among the characters that have already matched (similar to how we computed the prefix function).
* However, unlike last time, we don’t have to look for the length of a valid prefix all over again &mdash; we have already computed it and stored the corresponding length in the prefix function!
* Finally, if at any point the number of matched characters equals the length of the pattern, we will have found an occurrence of the pattern in the text.
* We can repeat the algorithm to find the next occurrence by looking for a shorter valid prefix length.


The Knuth-Morris-Pratt (KMP) Algorithm

In this lesson, we implemented the Knuth-Morris-Pratt Algorithm in Python to count the number of occurrences of a pattern in a given text. Even though we started out with a couple of brute-force approaches that resulted in large running times, we were able to employ some clever tricks and observations that allowed us to condense the underlying rudimentary details into something quite short and elegant! Here is a quick recap of what we did in this lesson:

* Reviewed the simplest way to find a pattern in a text using a brute-force algorithm.
* Explored ideas to improve over the brute-force algorithm by noticing that we can use information about the pattern &mdash; specifically, the prefixes and suffixes of the pattern &mdash; to skip characters in the text where the pattern cannot match.
* Accomplished this goal by computing the prefix function by finding up to each index the length of the longest proper suffix that is also a proper prefix in the pattern.
* Identified some clever manipulations to reduce the running time of computing the prefix function &mdash; all the way from O(n^3) down to O(n).
* Used the pre-computed values in the prefix function to perform faster pattern-matching via the Knuth-Morris-Pratt algorithm and observed its faster performance in comparison to Naive Pattern-Matching and the Rabin-Karp Algorithm.

We hope you learned a lot in this lesson and also enjoyed the process of algorithmic thinking! It is no small feat to be able to grasp the inner workings of complicated algorithms like Knuth-Morris-Pratt. Some of the greatest minds in history came up with these algorithms after decades of work! 

If something feels like it hasn't fully clicked yet, you are not alone! Feel free to come back to this lesson and go through it as many times as you need before things start making sense. In the meantime, you can head over to work on Projects to test and apply your understanding.

Review

In the last exercise, we brought down the running time of computing the prefix function to O(n<sup>2</sup>). But the question remains - can we do better? 

Believe it or not, the prefix function can be computed even faster - in just linear time! It does require grappling with some non-obvious ideas that can be a bit tricky to wrap your head around. But since we’ve already laid out important pieces of the puzzle and gradually progressed this far, it should only be a matter of time before we get it running.

Given that we know the length of each longest proper suffix up to an index that is also a proper prefix, the key question that we need to ask is &mdash; 
how can we use this information to derive the length of the longest proper suffix ending at the next index and is also a proper prefix?

```tex
\begin{array}{c}
\text{i}&0&1&2&3&4&5\\
 \text{pattern} & \text{A} & \text{B} &  \text{A} & \text{B} & \text{A} & \text{C} \\
\text{pi[i]} & 0 & 0 & 1 & 2 & ? & ?
\end {array}
```

Or, to put it in programming terms, the question we are asking is the following:

_Is `pattern[i]` equal to `pattern[pi[i - 1]]`?_

Why is it important for these two to be equal? Think about it &mdash; `pi[i - 1]` can also be interpreted as the length of the longest prefix that is also a proper suffix ending at `i - 1`. This means, if we index `pi[i - 1]` into the pattern as `pattern[pi[i - 1]]`, we are actually accessing the character next to that longest proper prefix as follows:

```tex
\begin{array}{c}
\text{i}&0&1&2&3&4&5\\
 \text{pattern} & \color{red} \fbox{\text{A}} & \color{green} \fbox{\text{B}} & \color{blue} \fbox{\text{A}} & \text{B} & \text{A} & \text{C} \\
\text{pi[i]} & 0 & 0 & 1 & 2 & ? & ?\\
\text{pi[i-1]} & 0 & 0 & 0 & 1 & 2\\
\text{pattern[pi[i-1]]} & \text{A} & \text {A} & \color{red} \fbox{\text{A}} & \color{green} \fbox{\text{B}} & \color{blue} \fbox{\text{A}} 
\end {array}
```

If the next character in pattern `pattern[i]` matches `pattern[pi[i-1]]`, this means `pi[i]` is longer than `pi[i-1]` by `1`. This is because we will be adding the same character `pattern[i]` to extend the valid suffix ending at `i-1` (which has already been discovered) to form the next valid suffix ending at `i` as follows:

```tex
\begin{array}{c}
\text{i}&0&1&2&3&4&5\\
 \text{pattern} & \text{A} & \text{B} & \text{A} & \text{B} & \fbox{\text{A}} & \text{C} \\
\text{pi[i]} & 0 & 0 & 1 & 2 & \color{green} 3 & ?\\
\text{pi[i-1]} & 0 & 0 & 0 & 1 & 2 & 3\\
\text{pattern[pi[i-1]]} & \text{A} & \text {A} & \text{A} & \text{B} & \fbox{\text{A}} & \text{B} 
\end {array}
```

In the opposite case that `pattern[i] != pattern[pi[i - 1]]`:

* Look for a valid suffix of a shorter length `j = pi[i - 1] - 1`.
* Index into the prefix function with this length as `pi[j]`. This gives the length of a valid suffix ending at index `j`.
* Index into `pattern` with this length as `pattern[pi[j]]`. This gives the character next to a valid prefix.
* Check to see if `pattern[i] == pattern[pi[j]]`. We can loop the entire process above from this point onwards.

Computing the Prefix Function Faster - Part 2

In the article we saw how to use the prefix function by hand; let’s implement it in Python!

The prefix function is typically implemented as a Python list. It is best understood (and appreciated) when implemented in increasing levels of efficiency. We will start off with the simplest way to do this, which would be to translate the following information from the previous exercise into code:

* A prefix function maps a pattern to an array of numbers.
* At each index, the array contains the length of the longest proper suffix up to that index in the pattern.
* The additional requirement is that the proper suffix must also be a proper prefix in the pattern.

Here is what the pseudocode would look like:

* Iterate through each index of the entire pattern whose prefix function we would like to build.
* For each index, iterate through all possible lengths of proper prefixes up to that index.
* For each proper prefix, check if there is a proper suffix that is equal to it.
* If there is one, set the value of the prefix function at the current index equal to the length of the proper prefix/suffix.

