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.