In this video you will learn in general how to efficiently construct suffix array; what are the steps and the substeps, and we will work out the details in the next few videos. But first, we need to go from suffixes to cyclic shifts. A cyclic shift of a string is a string we get if we write our initial string around the circle. And then start from any position and go through the whole circle. So for the initial string ababaa$, we can write down all the seven characters around the circle and then we will have the following cyclic shift. The initial string, the string babaa$a, which we'd gather if we start from character b and so on, moving around the circle. So these are the seven cyclic shifts of the initial string. And if we sort cyclic shifts instead of suffixes, let's see what happens, so these are all the cyclic shifts. Let's suppose we somehow manage to sort them in lexicographic order. And then we remove all the characters after the first occurrence of $, in each of those cyclic shifts. What we get is actually the suffix array we wanted. All those strings in the third column are suffixes of S in the sorted order. This is actually always true, we have a lemma that after adding to the end of string s character $, which is smaller then all other characters in that string. Sorting cycle shifts of the string and sorting suffixes of the stream is equivalent. We won't prove this lemma, we'll leave this as an exercise, we'll just use it in the following. Apart form total full cyclic shifts, which go the full circle starting from some position in the circle or string S, we'll also need partial cyclic shifts. And those are basically sub strings of cyclic string S. So it can take any position in the cyclic string and go a few characters in the order in the clockwise order from there, and you will get a partial cyclic shift. For example, if we take the same initial string and want to build all cyclic shifts of length 4, you can start from the first character a and you will get abab, or we can start from b and get baba, and so on. We will have again, seven different cyclic shifts of length four ending in the $aba. Now that we only go in the clockwise order, because this is the order when you try our cyclic string S as three a's written around the circle. So the general strategy for constructing a suffix array of the string S, is we start with a simple task, we sort all the single characters of the string S and those single characters are actually partial cyclic shifts of length one. So we assign L to one and now we have our base. We have sorted all the cyclic shifts of length L and then we will do iterations while L is still less than the length of the string, we will use our order of cyclic shifts of length L to sort the cyclic shifts of twice the length. And we will do that efficiently using the order of the current cyclic shifts of length L and thus will increase the length of the source suffixes twice. And then we will again increase it twice and so on and at some point L will be greater than or equal to the initial string S. And then we will have sorted the cyclic shifts of length greater than or equal to the length of the initial string and the order of those cyclic shifts is the same as the order of the full cyclic shifts of the initial string. So, this is the general strategy how we'll build the suffix array of the string. Now let's look at an example of application of these general strategy in practice. We use the same string in all the examples. So this is our string, and we start with sorting the partial cyclic shifts of length 1, which is just single characters of the string. And the smallest is $, then go four instances of letter a and then two instances of letter b. And six is the position of dollar in the string and 0, 2, 4 and 5 are the positions of letters a and 1 and 3 are the positions of letters b. In this case, the order of the partial cyclic shifts is 6, 0, 2, 4, 5, 1 and 3. And on the next step we go from cyclic shifts of length 1 to cyclic shifts of length 2 and their ordered changes. First goes $a, because $ is the smallest character and then goes a$, and then aa, and then two instances of ab, and then two instances of ba. And the order in this case is already 6, 5, 4, 0, 2, 1, 3, and that's because dollar is in position 6. And then a, after which there is a $, is in position 5. And then a, after which there is an a, is in position 4, and so on. On the next step we go from cyclic shifts of length 2 to cyclic shifts of length 4 and we get $aba and so on up to baba. And the order changes again it is 6, 5, 4, 2, 0, 3, 1. And on the last step we go from these partial cyclic shifts of length 4 to partial cyclic shifts of length 8, which are already longer than the initial stream. And we start from $ababaa$ and end with babaa$ab. And the order actually didn't change in this case. And now we have the order of cyclic shifts of length a which is the same as the order of the full cyclic shifts of the string s, which is in turn the same as the order of the suffixes of this string. So if we remove everything after the first occurrence of $ in all those partial cyclic shifts, we'll get the order of the size fixes of the initial string s. And so order is now our suffix array. And in the next video we'll start working through the details of this general strategy.
