Rotatie lexicografic minima

(Categoria Algoritmi, autor(i) Mircea Pasoi)

Acest articol reprezinta un studiu de caz al unei probleme care poate fi considerata "clasica", fiind studiata inclusiv de cunoscutul profesor Edsger Wybe Dijkstra. Deoarece problema a apaput recent la diverse concursuri de informatica, prezinta interes pentru cei care se pregatesc pentru participarea la acestea.

Enunt

In continuare vom prezenta doua formulari ale acestei probleme care au aparut recent la concursuri:

Cateodata programatorii au metode din cele mai diverse pentru a-ai ascunde parolele. De exemplu, sa vedem cum Billy "Hacker" Geits isi ascunde propriile parole. Billy isi alege un sir de caractere de lungime L < 100.000 format din litere mici ale alfabetului latin. Pentru acest sir de caractere Billy face toate cele L-1 deplasari circulare la stanga cu o pozitie si le pune unele sub altele. Dintre aceste L-1 siruri astfel obtinute, inaintea carora se trece sirul initial, se alege cel care este primul in ordine lexicografica, parola constituind-o un prefix al acestuia.
Scrieti un program care pentru un sir S dat determina pozitia celei "mai mici"(primei) deplasari in ordine lexicografica. Daca cel mai mic sir de caractere apare de mai multe ori, se se cere cea mai mica pozitie pe care acesta incepe.
(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 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)

Solutia naiva

O solutie triviala de complexitate O(N²) 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:

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

Solutia O(N*logN)

Precizam intai ca atat o solutie O(N*lg²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: