Learn

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?

$\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!

Instructions

1.

As we saw above, we do not have to check for proper prefixes of all possible lengths in the inner loop. Once we know the value of the prefix function in the previous index, we can narrow down our choices to the three cases above.

Let’s check the first case — the value can only increase by 1.

• Use an if condition to check to see if there is a proper prefix of length pi[i - 1] + 1 that is also a proper suffix of the same length.
• If there is one, this is the valid suffix/prefix length that we are looking for.
• Update the value of pi[i] to this length.
2.

If the first case is false, we need to check the second case — the value can NOT decrease at all i.e. stay the same.

• Use an elif condition to check to see if there is a proper prefix of length pi[i - 1] that is also a proper suffix of the same length.
• If there is one, this is the valid suffix/prefix length we are looking for.
• Update the value of pi[i] to this length.
3.

If the second case also turns out to be false, we finally need to check for all lengths from pi[i - 1] - 1 down to 0.

• Create an else branch.
• Inside the else branch, create a for loop to iterate through each length j from pi[i - 1] - 1 down to 0.
• Inside the for loop, check to see if there is a proper prefix of length j that is equal to a proper suffix of the same length.
• If there is one, this is the valid proper prefix/suffix length we are looking for.
• Update the value of pi[i] to this length and break out of the for loop.

But wait a minute! You created another for loop inside - shouldn’t this once again result in a running time of O(n^3)? Not quite. It turns out this extra loop can add a large constant factor (as opposed to the size of the input itself) at most, so the overall running time does indeed come down by a factor of n to O(n^2).