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.



Complete the function prefix_function() that takes a single parameter pattern.

  • First, create an outer for loop to iterate through all indexes i from 1 up to, but not including, len(pattern).
  • Then, create an inner for loop to iterate through proper prefixes of all possible lengths j from 1 up to, but not including, i+1.
  • Inside this loop, check to see if the proper prefix pattern[:j] of length j is equal to the proper suffix pattern[i-j+1:i+1] of the same length. If it is, update the value of pi[i] to be j.

Take this course for free

Mini Info Outline Icon
By signing up for Codecademy, you agree to Codecademy's Terms of Service & Privacy Policy.

Or sign up using:

Already have an account?