Nu exista diferente intre titluri.
Diferente intre continut:
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 înjumtete, este
uor de vzut c procesul nu se va repeta de mai mult de log2 N ori. Dei 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:
Nu exista diferente intre securitate.
Topicul de forum nu a fost schimbat.
