Siruri de sufixe

Acest articol a fost adăugat de Lucian Boca •amadaeus Intră aici dacă doreşti să scrii articole sau află cum te poţi implica în celelalte proiecte infoarena!

(Categoria Algoritmi, autori Adrian Vladu, Negruseri Cosmin)

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.

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.