p=. !siruri-de-sufixe?fig02.png!

*Pasul 0*:

Pasul 0:

p=. !siruri-de-sufixe?fig03.png!

*Pasul 1*:

Pasul 1:

p=. !siruri-de-sufixe?fig04.png!

*Pasul 2*:

Pasul 2:

p=. !siruri-de-sufixe?fig05.png!

*Pasul 3*:

Pasul 3:

p=. !siruri-de-sufixe?fig06.png!

h2. Cautarea
Deoarece sirul de sufixe ne ofera ordinea sufixelor lui $A$, cautarea unui string $W$ in $A$ se poate face simplu cu o cautare binara. Deoarece compararea se face in $O(|W|)$, cautarea va avea complexitatea $O(|W| lg n)$. Lucrarea [6] ofera structurii de date si algoritmului de cautare cateva rafinamente ce permit reducerea timpului la $O(|W| + lg n)$, dar autorii nu considera ca acestea sunt folositoare in concursurile de programare.

 
h2. Probleme de concurs
 
Autorii au incercat sa adune cat mai multe probleme ce pot fi rezolvate cu ajutorul sirurilor de sufixe. Parcurgerea tuturor problemelor la prima citire, ar putea fi greoaie pentru un cititor care a avut primul contact cu aceasta structura de date citind acest articol. Pentru a usura lectura problemele sunt asezate intr-o ordine crescatoare a dificultatilor.
 
h3. *Problema 1*: _Parola ascunsa_ (acm 2003, enunt modificat)
 
Consideram un sir de caractere de lungime $n$ $(1 ≤ n ≤ 100000)$. Sa se determine rotatia lui cilculara lexicografic minima. De exemplu, rotatiile sirului de caractere $alabala$ sunt:
$alabala$
$labalaa$
$abalaal$
$balaala$
$alaalab$
$laalaba$
$aalabal$
iar cea mai mica dintre ele in ordine lexicografica este $aalabal$.
 
h3. Solutie:
 
De obicei, in probleme unde apare rotatia unui sir dat, putem sa ne folosim de trucul de a concatena sirului de caractere acelasi sir pentru a simplifica problema. Dupa aceasta transformare problema ne cere subsecventa lexicografica minima de lungime n a noului sir. Ordinea subsecventelor de lungime n ale unui sir este egala cu ordinea sufixelor determinate de subsecventele date, deci ne putem folosi de arborii de sufixe pentru a rezolva aceasta problema.
 
O problema asemanatoare a fost propusa de unul dintre autori la concursul Bursele Agora, editia 2003-2004, care se putea rezolva pe aceiasi idee. Implementarea trebuia facuta atent pentru solutia oficiala era o rezolvare eficienta ce nu folosea aceasta structura de date.