Siruri de sufixe
(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.
Acest articol a fost adăugat de 
Alexandru Simion •sims_gl