Learn
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.
Instructions
1.
Complete the function prefix_function()
that takes a single parameter pattern
.
- First, create an outer
for
loop to iterate through all indexesi
from1
up to, but not including,len(pattern)
. - Then, create an inner
for
loop to iterate through proper prefixes of all possible lengthsj
from1
up to, but not including,i+1
. - Inside this loop, check to see if the proper prefix
pattern[:j]
of lengthj
is equal to the proper suffixpattern[i-j+1:i+1]
of the same length. If it is, update the value ofpi[i]
to bej
.
Take this course for free
By signing up for Codecademy, you agree to Codecademy's Terms of Service & Privacy Policy.