Hi, in this video, you will learn how to efficiently compute all the values of the prefix function in an efficient way. We'll start with an example. We're given a pattern, P, and we want to compute its prefix function, s. We'll start with position 0, and we'll fill in 0. And S of 0 is always 0, because the prefix of pattern ending in position 0 has length 1, and has no known empty borders. Why don't we move on to the character in position one, which is b. And we compare it with the next character after the end of the previous border. The end of the previous border was before the pattern P starts, so the next character is a. And we compare a with b, they are different. And so the value of the prefix function is again zero, because we cannot take border of the empty border. And so we have to acknowledge that the prefix function is again zero. Now we'll look at the next character a and we'll look at the next character after the end of the previous border which is again the a in position 0. And we see that these characters are the same. So we increase the previous value of s by one. And our value of prefix function for position 2 is 1, and now our current border is of length 1 and it contains just the letter a in position 0. And we look at the next character which is b. And we need to compare it with the character right after the end of the current border, which is the b in position one. And those characters are the same, so we increase the length of the previous border by one. And we write down that s of three is equal to two. And our current border is of length two, and it is ab. Now we'll look at the next character a. We need to compare it with the next character after the current border, which is a in position two. And they're the same. So again, increase the value of our prefix function by a and we increase the length of the current boarder and it becomes aba. The next character is b, we need to compare it with the next character after the end of our border and they are again, the same. So, we increase the value of our prefix function by one and it becomes four. And our border is abab. Now we'll look at the character c, we need to compare it with the next character after the end of the current border. And they are different. So what we need to do is to take the longest border of our current border, and we'll look at position three, and s of 3 is two. And so the longest border of abab is just ab. And now, we need to compare our current character c with the next character after the end of that border, which is a. And they're again different, so we need to take the longest border of our current border, and that has length 0. So, that will be empty string. And so now, we need to compare our current character with the first character of the pattern, which is a. And they're again different. So we'll write down that our prefix function is 0. We move on to the next character a. We compare it with the next character after the end of the border which is the first character of pattern. And they are the same so we write down 1 as the value of our prefix function. Now the border has length 1 it is just string a. We look at the next character a, and we compare it with the character right after the end of the current border. They're different, so we need to take the longest border of our current border, which is empty string. And so we need to compare current character with the first character of the pattern. They're the same, so we write down 1 as the value of our graphics function and the current border has length 1. And finally, we go to the symbol b in the end of the pattern and we need to compare it with b in position 1. They are the same so increase the value of the prefix function by 1 and write down 2 as the value of the prefix function for the last position. This was how the computation of the prefix function values works on an example. And now let's look at the pseudo code which can compute these values for any string P. It will return an array of values s, which has the length the same as the length of the string, and which will contain the values of the prefix function for positions from 0 to length of the string minus 1. We start by initializing this array, and we'll write down s of 0 equal to 0, as I explained. And we also need additional variable border which will contain the length of the current border at all times. And then this for loop where position I goes from one to the last position in the string will actually compute as of I. At first we need to look at our current character P of I, and we need to compare it with the character right after the end of our current border. For example if the length of our current border is 2 then the border itself contains characters in positions 0 and 1. And so the next character right after the end of the current border is in position two. This is why we compare character in position i, P of i, with the character in position border. P of border. So we compare them and as soon as they are the same, we know what to do. But, if they're different we need to take the longest border of our current border. How to do that? Our current border ends in position border minus 1. We know that the length of its longest border is contained in the corresponding value of the prefix function. So we assign value s of border minus 1 to our variable border. And we only end this while loop if either current character p of i is the same as the character P of border or our border became empty string. After that we compare our current character again with the character in position border. And either they are the same, then we increase our current border by one. And that is the value we need to assign to our prefix function. Or, they are still different after border became zero. And so, our current prefix function value should be zero. And in the event of the for loop iteration, we just assign the value to the prefix function. And that will return the array with values of the prefix function. And we state that this algorithm runs in linear time. Why is that? Well, let's first forget for a moment about the inner while loop. Then what we are left with is initialization which obviously works in linear time. And the for loop with linear number of iterations. And everything inside for loop, but for the while loop, for which we don't account now, runs in constant time. So, everything but for the inner while loop works in linear time. Now on each iteration of the four loop, the while loop could take in theory as many as linear number of iterations. And if we sum all that up, that would be quadratic in the length of the pattern. And now, we will bound the total number of the while loop iterations by big O of the length of the pattern. And to do that, we will consider the graph of the values of the prefix function. Here, the horizontal axis contains positions in the string. And vertical axis contains values of the prefix function. The graph always starts in .00. Because s of 0 is 0. And it can stay the same, it can increase, it can decrease, but it never becomes less than zero because prefix function is always non-negative by definition. And also, it can never increase by more than one on each iteration. And our variable border in the code behaves the same way. It can be increased by at most one on each four loop iteration. But after each successful iteration of the inner while loop it gets decreased by at least one, because we consider the current border. We look at the next character and if it's different from the character in position i we take the longest border of our current border which is strictly shorter. So our border value decreases. And so all in all, border can increase at most length of the pattern times. And it is decreased by at least 1 on each iteration of the while loop. And border is also always non-negative. It means that it can be decreased at most, we go off length of the pattern times. And so there are at most linear number of while loop iterations in total. Now you know how to compute prefix function efficiently in linear time in the length of the pattern. But how to actually solve the initial problem? How to find the pattern in the text? That you will finally learn in the next video.