sfarsit pentru
sfarsit cat timp
scrie L[1]

==

==
 
Spre exemplu, pentru sirul S = ("m", "i", "s", "s", "i", "s", "s", "i", "p", "p", "i") lista va contine initial elementele {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
La primul pas se efectueaza (caracterele ingrosate sunt cele ce se vor compara):
R0 = mississippi > R1 = ississippim
R2 = ssissippimi = R3 = sissippimis
R4 = issippimiss < R5 = ssippimissi
R6 = sippimissis > R7 = ippimississ
R8 = ppimississi = R9 = pimississip
Lista va fi acum {1, 2, 4, 7, 8, 10}
Pasii urmatori sunt:
R1 = ississippim < R2 = ssissippimi
R4 = issippimiss > R7 = ippimississ
R8 = ppimississi > R10 = imississipp
L = {1, 7, 10}
R1 = ississippim > R7 = ippimississ
L = {7, 10}
R7 = ippimississ > R10 = imississipp
L = {10}
 
_TODO : add image_
 
h2. Solutia O(N)
 
Vom incerca acum sa obtinem un algoritm de complexitate liniara folosind alte idei de rezolvare. Algoritmul pe care il vom propune in continuare functioneaza ca si algoritmul trivial mentionat mai sus, anume parcurgand rotatiile succesiv. La fiecare pas se vor pastra trei variabile min, p, l cu semnificatia ca rotatiile R ~0~, R ~1~, ... R ~p-1~ au fost parcurse pana acum, iar R ~min~ este o rotatie dintre acestea care ar putea fi cea lexicografic minima (toate celelalte din cele parcurse sigur nu pot fi solutia finala). De asemenea, variabila l va semnifica ca primele l caractere din R ~min~ sunt egale cu primele l caractere din R ~p~, R ~p~ fiind urmatoarea rotatie ce va fi procesata. Cunoscand aceste informatii, la fiecare pas se va compara al l+1-lea caracter din R ~min~ (S[min+l]) cu al l+1-lea din R ~p~ (S[p+l]), iar in functie de rezultat se va lua o decizie:
 
* S[min+l] = S[p+l] -> se va incrementa variabila l cu o unitate deoarece inca o pereche de caractere
se potrivesc
* S[min+l] < S[p+l] -> putem trage imediat concluzia ca R ~min~ < R ~p~ , iar mai mult, din faptul ca primele l caractere se potrivesc putem spune ca R ~min+i~ < R ~p+i~ pentru 0 <= i <= l; cum R ~min~ era rotatia "candidata" la solutia finala dintre R ~0~, R ~1~, ... R ~p-1~ si este mai mica ca R ~p~, iar pentru orice R ~p+i~ (1 <= i <= l) exista R ~min+i~ < R ~p+i~, despre care se stie ca nu poate fi solutia finala, R ~min~ va repezenta in continuare rotatia candidata la solutie dintre R ~0~, R ~1~, ... R ~p-1~, R ~p~, R ~p+1~, ... R ~p+l~. Asadar p va deveni p+l+1, iar l va deveni 0 (deoarece nu se cunosc inca informatii despre R ~min~ si R ~p+l+1~)
*