h2. Introducere

Un domeniu important in algoritmica folosit� în practic� este acela al algoritmilor pe �iruri de caractere. Astfel la concursurile de programare sunt prezente foarte multe probleme de prelucrare �i procesare a unor �iruri de caractere. �n cadrul concursurilor �i antrenamentelor mulţi dintre noi s-au lovit de probleme ce s-ar fi rezolvat u�or dac� se reu�ea în mod eficient determinarea existenţei unui cuvânt ca subsecvenţ� a unui alt cuvânt. Vom prezenta o structura versatil� ce permite acest lucru, înlesnind de multe ori realizarea altor operaţii utile pe un string dat.

Un domeniu important in algoritmica folosita în practica este acela al algoritmilor pe siruri de caractere. Astfel la concursurile de programare sunt prezente foarte multe probleme de prelucrare si procesare a unor siruri de caractere. În cadrul concursurilor si antrenamentelor multi dintre noi s-au lovit de probleme ce s-ar fi rezolvat usor daca se reusea în mod eficient determinarea existentei unui cuvânt ca subsecventa a unui alt cuvânt. Vom prezenta o structura versatila ce permite acest lucru, înlesnind de multe ori realizarea altor operatii utile pe un string dat.

h2. Ce sunt �irurile de sufixe (suffix arrays)?

h2. Ce sunt sirurile de sufixe (suffix arrays)?

Pentru a avea o idee mai bun� despre suffix arrays, vom face înainte o scurt� prezentare a structurii de date numit� în englez� trie �i a arborilor de sufixe (suffix trees [1]) care sunt o form� special� a structurii de date trie. Un trie este un arbore menit s� stocheze �iruri. Fiecare nod al lui va avea în general un num�r de fii egal cu m�rimea alfabetului �irurilor de caractere care trebuies stocate. �n cazul nostru, cu �iruri ce conţin litere mici ale alfabetului englez, fiecare nod va avea cel mult 26 de fii. Fiecare muchie care porne�te din tat� spre fii �i va fi etichetat� cu o liter� distinct� a alfabetului. Etichetele leg�turilor de pe un drum de la r�d�cina pân� la o frunz� vor alc�tui un cuvânt stocat in arbore. Dup� cum se observ�, c�utarea existenţei unui cuvânt în aceast� structur� de date este foarte eficient� �i se realizeaz� în complexitate O(M), unde M e lungimea cuvântului. Astfel, timpul de c�utare nu depinde de num�rul de cuvinte pe care trebuie s� îl gestioneze structura de date, fapt ce face aceast� structur� ideal� pentru implementarea dicţionarelor.

Pentru a avea o idee mai buna despre _suffix arrays_, vom face înainte o scurta prezentare a structurii de date numita în engleza _trie_ si a _arborilor de sufixe_ (suffix trees [1]) care sunt o forma speciala a structurii de date trie. Un trie este un arbore menit sa stocheze siruri. Fiecare nod al lui va avea în general un numar de fii egal cu marimea alfabetului sirurilor de caractere care trebuies stocate. În cazul nostru, cu siruri ce contin litere mici ale alfabetului englez, fiecare nod va avea cel mult 26 de fii. Fiecare muchie care porneste din tata spre fii si va fi etichetata cu o litera distincta a alfabetului. Etichetele legaturilor de pe un drum de la radacina pâna la o frunza vor alcatui un cuvânt stocat in arbore. Dupa cum se observa, cautarea existentei unui cuvânt în aceasta structura de date este foarte eficienta si se realizeaza în complexitate O(M), unde M e lungimea cuvântului. Astfel, timpul de cautare nu depinde de numarul de cuvinte pe care trebuie sa îl gestioneze structura de date, fapt ce face aceasta structura ideala pentru implementarea dictionarelor.
Sa vedem acum ce este un trie de sufixe:
Dat fiind un string $A$ = $a{~0~}a{~1~}…a{~n–1~}$, notam cu $A{~i~}$ = $a{~i~}a{~i+1~}…a{~n–1~}$ sufixul lui $A$ care începe la pozitia $i$. Fie $n$ = lungimea lui $A$. Trie-ul de sufixe este format prin comprimarea tuturor sufixelor $A{~1~}…A{~n–1~}$ într-un trie, ca în figura de mai jos.
Trie-ul de sufixe corespunzator stringului $abac$ este:
 
Operatiile pe aceasta structura se realizeaza extrem de usor:
* verificarea daca un string $W$ este substring al lui $A$ – este suficienta parcurgerea nodurilor, începând din radacina si urmarind muchiile etichetate corespunzator caracterelor din $W$ (complexitate $O(|W|)$)
* cautarea celui mai lung prefix comun pentru doua sufixe ale lui $A$ – se aleg nodurile $u$ si $v$ ale trie-ului corespunzatoare sfârsitului celor doua prefixe, iar prin aplicarea unui algoritm de gasire a LCA (least common ancestor / cel mai apropiat stramos comun) se gaseste nodul corespunzator sfârsitului prefixului cautat. De exemplu, pentru $abac$ si $ac$ se gasesc nodurile $5$ si $6$. Cel mai apropiat stramos comun al lor este $2$, de unde rezulta prefixul $a$. Autorii va recomanda articolul [2] pentru o rezolvare în $O(sqrt(n))$, [3] pentru o prezentare accesibila a unei rezolvari în $O(log n)$ sau $O(1)$, si articolul [4] pentru un algoritm _“state of the art”_.
* gasirea celui de-al $k$-lea sufix în ordine lexicografica - (complexitate $O(n)$, cu o preprocesare corespunzatoare). De exemplu al $3$-lea sufix al sirului $abac$ este reprezentat în trie-ul nostru de a $3$-a frunza.