R' = { 1, 2, 4, 6, 4, 5, 3, 7 }
SR' = {0, 1, 6, 7, 2, 5, 3, 7 }

h3. Pas 2:

Pas 2:

Sortam sufixele de tip 0.

Orice sufix de tip 0 poate fi considerat ca o pereche (caracter, sufix de tip 1): S0,i = Ci + S1,i+1
Se poate folosi radix sort pentru a sorta aceste perechi.

h3. Pas 3:

Pas 3:

Interclasam cei doi vectori sortati de sufixe. Avem doua cazuri la comparare. Acestea pot fi reduse la compararea sufixelor de tip 1 cu sufixe de tip 2 astfel:

# sufix de tip 0 (Si) cu sufix de tip 1 (Sj) -> (caracter, sufix de tip 1) - (caracter, sufix de tip 2) : (Ci + S1,i+1) - (Cj + S2,j+1)
# sufix de tip 0 (Si) cu sufix de tip 2 (Sj) -> (caracter, caracter, sufix de tip 2) - (caracter, caracter, sufix de tip 1) : (Ci + Ci+1 + S2,i+2) - (Cj + Cj+1 + S1,j+2)

1. sufix de tip 0 (Si) cu sufix de tip 1 (Sj) -> (caracter, sufix de tip 1) - (caracter, sufix de tip 2) : (Ci + S1,i+1) - (Cj + S2,j+1)
2. sufix de tip 0 (Si) cu sufix de tip 2 (Sj) -> (caracter, caracter, sufix de tip 2) - (caracter, caracter, sufix de tip 1) : (Ci + Ci+1 + S2,i+2) - (Cj + Cj+1 + S1,j+2)

h2. Analiza complexitatii:

Analiza complexitatii:

Se observa ca fiecare pas poate fi efectuat in timp liniar.
Algoritmul se repeta pe un sir de lungime 2N / 3. De aici complexitatea poate fi data de recurenta T(N) = T(2N / 3) + O(N) => T(N) = O(N).