Hi, in this video you will learn how to implement the transition phase of

the suffix array construction algorithm.

In the transition phase,

you assume that you have already sorted cyclic shifts of some length, L.

And you know not only their order but also their equivalence classes,

and you need to sort based on that cyclic shifts of length 2L.

The main idea is the following.

Let's denote by Ci cyclic shift of length L starting in position i,

and by Ci prime the doubled cyclic shift starting in i.

That is, cyclic shift of length 2L, starting in position i.

Then, Ci prime is equal to Ci concatenated with Ci + L.

So we just take string Ci, we take string Ci + L, put it after string Ci.

And the total string of length 2L is equal to string Ci prime.

And so to compare Ci prime with Cj prime it's sufficient

to separately compare Ci with Cj, and Ci + L with Cj + L.

And we already know the order of the cyclic shifts of length L.

So instead of comparing them directly, we can just look in the array

of their order and determine which one is before which one.

And that one is going to be smaller or the same as the other one.

And also, we have the area with equivalence classes.

And so we can determine whether two cyclic shifts of length L are really equal,

or they're different, by looking in the array for equivalence classes and

comparing their equivalence classes.

So basically we can compare two cyclic shifts of length L in constant time.

And that is why we can sort the doubled cyclic shifts faster.