Hi, in this video you will learn how to update the equivalence classes of the double cyclic shifts after sorting them. And that will be the last step before we can actually present the whole algorithm for building the suffix array. So to update classes, we need to compare the pairs of single shifts which constitute the double cyclic shifts which we have just sorted. We have already sorted the pairs. So, we just need to go through them in order and compare each pair to the previous pair. If it's the same, then we need to assign it to the same class. If it's bigger, then we need to create a new class and assign it to this pair. To compare the pairs, we can compare them separately by first element and then by second element. Of course the elements of the pairs are cyclic shifts and we don't want to compare them directly character by character. But, for that we already know their equivalent class is of the single cyclic shift, and we can just compare the equivalence classes instead of the cyclic shifts themselves. So we can compare any two pairs of single cyclic shifts in constant time. Let's look at an example. S is our initial string and suppose we've already sorted the doubled cyclic shifts of length 2, and our initial cyclic shifts were of length 1. So we have our array class of the equivalence classes of the cyclic shifts of length 1, which is basically letters. And remember that this array has one element which is equal to 0 which corresponds to the dollar, and it is in position six. We have four elements which are equal to 1 which correspond to letters a in positions 0, 2, 4, and 5. And we have two elements which are equal to 2 which correspond to letters b in positions 1 and 3. So these are the equivalence classes of the single cyclic shifts. Now for the double cyclic shifts we can write them down in the order because we've already sorted them. And we know the new order which is the order of the double cyclic shifts. They go 6, 5, 4, 0, 2, 1, 3. From $a to ba. And along with each doubled cyclic shift, we'll also write down the pair of the equivalence classes of its halves. For example, for $a, the equivalence class for dollar is 0 and the equivalence class for a is 1. So it corresponds to pair 0, 1. And for ab, for example, the equivalence class of a is 1, and equivalence class of b is 2. So we write down the pair 1, 2. These are the pairs of the equivalents classes of the single cyclic shifts. And now we need to compute the equivalence classes of the doubled cyclic shifts. And write them down into the array newClass. To do that, we go through the double cyclic shifts in the sorted order using array newOrder. And we start from the first one, which is $a. And we write down value 0 for its class in position 6 because it is in position 6 as we see from the array newOrder. Then we'll proceed to the next doubled cyclic shift. And to assign class to it, we need to compare it to the previous one. And of course in this picture, we could compare directly these double cyclic shifts the previous one, and determine that it's different. But in practice, in general stage we don't want to do that. And instead of comparing the cyclic shift directly, we compare the pairs of numbers written to the right from them and we see that the pair 1, 0 is different from the pair 0, 1. And we do this comparison just by two comparisons of numbers instead of comparing full cyclic shifts. As far as this double cyclic shift is different, we need a new class for it. And we assign it to class 1. And write it into position 5 because this is the position for this double cyclic shift as we see from array newOrder. Now we proceed to the next one which is aa. We again compare it with the previous one, by pairs. 1, 1 on 1, 0 are different pairs, so we write down a new class again, class 2 in position 4, as given in the array newOrder. Then proceed to ab. It is again different. 1, 2 is different from 1, 1. So we create a new class 3 and put it in position 0 as given by array newOrder. Then we'll look at ab again and it is the same as the previous ab. As we see from pairs 1,2, 1,2 which are equal. So, we don’t need to create a new class. We write down the same class 3 into position 2 as given by the array newOrder. Now look at ba, it is different from ab. So, we create new class 4. And then the second ba's of course are equal to the previous ba, so we write down 4 in position 3 as given by the newOrder array. So this is how it works, updating of the classes. Now let's look at the code. So the procedure UpdateClasses does exactly the same as we did in the example. It takes as input array newOrder, the order of the double cyclic shifts. It also takes classes of the single cyclic shifts. And also it takes the length of the single cyclic shifts as inputs. And it will return the array with equivalent classes of the double cyclic shifts as a result. First we initialize variable n with the size of newOrder. Basically n will be equal to the length of the string but we don't have string as an input so we need variable to compute it's length. And we initialize the array newClass with an array of size n. And first we assign class 0 to the smallest double cyclic shift which is given by newOrder of 0. And then we go through all the double cyclic shifts from position 1 to n-1, and we need to compare the double cyclic shift number i with the double cyclic shift number i-1. To do that, we first compute their starting positions. Cur is the starting positions of the doubled cyclic shift number i, and prev is the position of the previous one. And also need to compute the positions of their middle of the position where their second half starts. So, we need to compare them half by half. So, cur and prev are the starting positions of the doubled cyclic shifts and mid and midPrev are the starting positions of their second halves. To compute them, we just take the position clockwise to the right by L. So we add L and take everything modular n. Which is the length of the string. And now we do just what we did in the example. We compare the classes of the current position and the previous position. And the classes of the starting positions of the second halfs. If at least one of the halfs is different, it means that the pair is different from the previous one. And we need to create a new class, increase the current class by 1 and assign to the current position. Otherwise, the pair is the same as the previous one, and we don't need to create a new class. We just assign the same class to the current position. And we then return the array with the new classes of the double cyclic shifts. We state that the running time of this algorithm UpdateClasses is linear. And that's easy to prove because, well basically, we only have one for loop with linear number of iterations and constant time operations happening inside.
