Hi, in the previous video, we proved some properties of the prefix function. And got some intuition on how to compute the values of the prefix function, one by one from left to right. In this video, we'll consider a specific example of computing prefix function that way. And then we'll implement the whole algorithm in the general case. First let's look at this example of a pattern and compute values of the prefix function for this pattern one by one from left to right using the properties that we know. First, we compute prefix function for position 0, and it is always equal to 0 because for a string of length 1, the only border is the empty string. Now we move one position to the right and we compute prefix function for the perfect ending in this position. To do that, we need to compare this character at this position with the character right next after the end of the longest border of the previous prefix. In this case, this is the character a, right after the end of the empty border. These characters are different, which are marked with red. And so, we need to compute the next shorter border of the previous prefix and compute b with the character right after the end of this border. But it turns out that we already have the empty border. And when we have empty border, there is no shorter border. And actually this means that there is no border for the string ending in this position. And so the prefix function is again equal to 0 in this case. Now we'll consider the next position ending in character a. And we need to compare this character to the character right after the end of the longest border of the previous prefix. Longest border of the previous prefix is an empty string. And the character right after it is the character a in the first position. And it turns out that our new last character is equal to the character right after the end of the previous border. In this case, we know that prefix function for this position is just equal to the prefix function for previous position plus 1. So in this case it is equal to 1. And now we also save the longest border. It is now for the first time non empty. And we marked the longest border of the last prefix that we considered with yellow color. So now, we consider the prefix function for position ending in character b. And now we need to compare this b to the character right after the end of the longest border of the previous prefix, which is marked with yellowish a. And the next character is this b. And they are equal. So it means that the prefix function for this position is equal to the prefix function for the previous position plus 1 which is 2. And now, the length of the longest border is 2. And we mark the longest border itself a, b with yellow. We consider the next character. We need to compare it with the character right after the end of the yellow border ab which is a. They are equal. So the prefix function for this position is 1 plus prefix function for previous position which is 3. And the longest border is now aba. Now we consider prefix function for the next position. We need to compare this b with the character right after the yellow border which is b, they're equal. So prefix function is 1 plus prefix function for the previous position. Now we consider the next position with character c, we need to compare this character with the first character right after the yellow border ab ab. This character is a, and they are different. In this case, we shouldn't stop yet. We should try to compare c, the last character with the first character after the longest border of the current longest border which is ab ab. And each longer border we know that it has length 2, because the prefix function for the corresponding position is written right under the last character of the current border which is 2. So that longer border is ab. So now we need to compare our character c which is the last character with the character right after the end of this yellow border which is a, again, there are different. So now we need to take the longest border of our current border and compare c with the character right after the end of it. The longest border of ab has like 0, it is empty string because we have the prefix function for the corresponding position written right under the last character b of the current border ab. So now, we need to compare our last character c with the first character right after the end of the empty prefix which is a. Again, there are different. And in this case, we have to write down the value of prefix function which is 0. Now we move to the next character. We need to compare it to the first character right after the end of the longest border of the previous prefix which is the first character a, they're the same. So the prefix function is just 1 plus prefix function of the previous position which is 1 and now the longest border is a. We move to the next position. We need to compare this a to the next character after the end of the current longest border first and current longest border is a. The next character is b, a and b are different. So at this point, we don't need to stop, we need to compute the longest border of the current longest border and it has like 0. It is written right under the last character of the current longest border of a. So we need to move to the case when the longest border is an empty string. And we need to compare our last character a with the character right next after the end of the current longest border, which is again a, which is the first letter. They are the same. So in this case, prefix function is equal to 1. Now we move to the next character b. We need to compare it with the character right after the end of the current longest border, which is b. They are the same. And so the prefix function is equal to 1 plus the previous longest border which is 2. And now we've finished the computation of the prefix function in this example. And in the next video, we're going to implement this algorithm in the general case.
