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.