Sirul cautat este prima permutare circulara in ordine lexicografica a sirului dat. Notam cu $S{~i~}^k^$ substringul de lungime $k$ ce incepe la pozitia $i$. Fie $S{~i~}^n^$ cel mai mic substring in ordine lexicografica de lungime $n$ al sirului obtinut prin concatenare.  Presupunand prin absurd ca $s(i+n-1) < n$ ar insemna ca exista un $i'$ $(i < i' &le; j)$ astfel incat $S{~i'~}^j-i'+1^$ este lexicografic mai mic decat $S{~i~}^n^$. Dar din conditia impusa de enunt avem $S{~i'~}^j-i'+1^ > S{~i'~}^n^$. Dar $S{~i'~}^n^ > S{~i~}^n^$ => contradictie.
Desi exista un algorirm de complexitate $O(n)$ pentru aceasta, metoda preferata de autor (si cu care a obtinut punctaj maxim in timpul concursului) a fost folosirea sirurilor de sufixe, ca in problema anterioara.

 
h3. *Problema 3*: _substr_ (baraj 2003)
 
Se da un text format din $N$ caractere (litere mari, litere mici si cifre). Un substring al acestui text este o secventa de caractere care apar pe pozitii consecutive in text. Fiind dat un numar $K$, sa se gaseasca lungimea celui mai lung substring care apare in text de cel putin $K$ ori $(1 ≤ N ≤ 16384)$.
 
h3. Solutie:
 
Avand sufixele textului sortate, iteram cu o variabila $i$ de la $0$ la $N – K$ si calculam cel mai lung prefix comun intre sufixul $i$ si sufixul $i + K – 1$. Prefixul maxim determinat in cursul acestei parcurgeri reprezinta solutia problemei.
 
h3. *Problema 4*: _ghicit_ (baraj 2003)
 
Tu si cu Taranul jucati un joc neinteresant. Tu ai un sir de caractere mare. Taranul iti spune un alt sir de caractere, iar tu trebuie sa raspunzi cat mai repede daca sirul respectiv este sau nu o subsecventa a sirului tau.
Taranul  iti pune multe intrebari si, fiindca esti informatician, te-ai gandit ca ar merge mai repede daca ai sti dinainte toate sirurile despre care te poate intreba.
Inainte de a face toata acesta munca te-ar interesa numarul total de subsecvente distincte ale sirului tau, ca sa stii daca are sens sa te apuci de acesta treaba sau nu.
Scrieti un program care afla numarul de subsecvente distincte ale unui sir de caractere dat. $(1 ≤ lungimea sirului ≤ 10 000)$
 
h3. Solutie:
 
Aceasta problema ne cere, de fapt, sa calculam numarul de noduri (fara radacina) ale trie-ului de sufixe asociat unui string. Fiecare secventa distincta din sir este determinata de drumul unic pe care il parcurgem in trie-ul de sufixe cand cautam acea secventa. Pentru exemplul $abac$ avem secventele $a$, $ab$, $aba$, $abac$, $ac$, $b$, $ba$, $bac$ si $c$, acestea sunt determinate  de drumul de la radacina trieului spre nodurile $2$, $3$, $4$, $5$, $6$, $7$, $8$ si $9$ in aceasta ordine. Cum constructia trie-ului de sufixe are complexitate patratica, iar construirea unui arbore de sufixe este anevoioasa, este preferabila o abordare prin prisma sirurilor de sufixe. Obtinem sirul sortat de sufixe in $O(n lg n)$, dupa care cautam pozitia in care fiecare pereche de sufixe consecutive difera (folosind functia $lcp$) si adunam la solutie restul caracterelor. Complexitatea totala este $O(n lg n)$.
 
h3. *Problema 5*: _seti_ (ONI 2002, enunt modificat)
 
Se da un string de lungime $N$ $(1 ≤ N ≤ 131072)$ si $M$ stringuri de lungime cel mult $64$. Se cere sa se numere aparitiile fiecarui string din cele $M$ in stringul mare.
 
h3. Solutie:
 
Se procedeaza ca la siruri de sufixe, numai ca este suficient sa ne oprim dupa pasul 6 unde am calculat relatia de ordine intre stringurile de lungime $2^6^ = 64$. Avand substringurile de lungime 64 sortate, fiecare query este rezolvat cu doua cautari binare. Complexitatea algoritmului este $O(N lg 64 + M * 64 * lg N) = O(N + M lg N)$.