daca Rmin > Ri atunci min <-i;
sfarsit pentru
scrie min

==
 
h2. Solutia O(N*logN)
 
Precizam intai ca atat o solutie O(N*lg^2^N) cat si una O(N*lgN) pot fi obtinute folosind structura de date "siruri de sufixe" [1]. Din pacate aceste solutii nu sunt foarte usor de implementat, iar constanta din notatia O este destul de mare cat sa merite cautarea unei solutii alternative. Vom prezenta in continuare o solutie de complexitate O(N*lgN), mult mai usor de implementat odata ce este inteleasa.
 
Primul pas pentru obtinerea acestei solutii este folosirea unei strategii de tip "turneu", si anume la fiecare iteratie se pastreaza o lista cu rotatiile care ar putea fi minime. Initial lista va avea toate cele N rotaii, iar de fiecare data se iau rotatiile dou cate dou din list 
i se elimin cea mai mare dintre cele
dou din punct de vedere lexicografic. Procesul se reia pân când se obine o list cu un singur element,
reprezentând rotaia minim. Cum la fiecare pas numrul de elemente din list se înjumte
te, este
u
or de vzut c procesul nu se va repeta de mai mult de 
log2 N ori. De
i la prima vedere acest
algoritm are timpul de rulare O(N2*lg N), vom arat în continuare ca sunt suficiente O(N) comparaii de
caractere per total la fiecare repetare:

==