h1. Siruri de sufixe

== include(page="template/implica-te/scrie-articole" user_id="sims_gl") ==

== include(page="template/implica-te/scrie-articole" user_id="amadaeus") ==

(Categoria _Algoritmi_, autori _Adrian Vladu, Negruseri Cosmin_)
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.
h2. Ce sunt ÅŸirurile 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.

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.
 
h2. Ce sunt �irurile 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.