_(ACM 2003-2004, regionala Europei de sud-est)_
Intr-un seif se afla niste documente pe care trebuie sa le extrageti. Problema este ca seiful este prevazut cu un terminal care necesita introducerea unei parole pentru a putea deschide seiful. La accesarea seifului, pe ecranul terminalului este afisat un cuvant cheie format din litere mici ale alfabetului englezesc. Parola este data de cea mai mica rotatie la stanga (in ordine lexicografica) a cuvantului cheie.

Fisierul de intrare password.in contine pe prima linie un sir de caractere format din litere mici ale alfabetului englezesc. Lungimea sirului din fisierul de intrare este un numar întreg cuprins între 1 si 100.000.
Fisierul de iesire password.out trebuie sa contina un singur numar care reprezinta numarul de deplasari circulare la stanga ale sirului din fisierul de intrare necesare pentru a obtine parola de acces ceruta. Daca exista mai multe solutii va fi aleasa cea care necesita un numar minim de deplasari circulare la stanga.

Fisierul de intrare _password.in_ contine pe prima linie un sir de caractere format din litere mici ale alfabetului englezesc. Lungimea sirului din fisierul de intrare este un numar intreg cuprins intre 1 si 100.000.
Fisierul de iesire _password.out_ trebuie sa contina un singur numar care reprezinta numarul de deplasari circulare la stanga ale sirului din fisierul de intrare necesare pentru a obtine parola de acces ceruta. Daca exista mai multe solutii va fi aleasa cea care necesita un numar minim de deplasari circulare la stanga.

_(Bursele Agora 2003-2004, Runda 44)_

h2. Solutia naiva

h2. Solutia naiva
 
O solutie triviala de complexitate O(N^2^) poate fi obtinuta parcurgand succesiv rotatiile si tinand cont de faptul ca compararea a doua siruri are complexitatea O(N) in cel mai defavorabil caz. Prezentam in continuare pseudocodul:
 
== code(c) |
 
min <- 0; R0 <- S;
 
pentru i = 1, N-1 executa
construieste Ri in functie de Ri-1
daca Rmin > Ri atunci min 
 i;
sfarsit pentru
scrie min
==