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

Pentru a avea o idee mai buna despre _suffix arrays_, vom face inainte o scurta prezentare a structurii de date numita in 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 in general un numar de fii egal cu marimea alfabetului sirurilor de caractere care trebuies stocate. In cazul nostru, cu siruri ce contin litere mici ale alfabetului englez, fiecare nod va avea cel mult 26 de fii. Fiecare muchie porneste din tata spre fii si va fi etichetata cu o litera distincta a alfabetului. Etichetele legaturilor de pe un drum de la radacina pana la o frunza vor alcatui un cuvant stocat in arbore. Dupa cum se observa, verificarea existentei unui cuvant in aceasta structura de date este foarte eficienta si se realizeaza in complexitate $O(M)$, unde $M$ e lungimea cuvantului. Astfel, timpul de cautare nu depinde de numarul de cuvinte pe care trebuie sa il gestioneze structura de date, fapt ce face aceasta structura ideala pentru implementarea dictionarelor.

Pentru a avea o idee mai buna despre _suffix arrays_, vom face inainte o scurta prezentare a structurii de date numita in engleza _trie_ si a _arborilor de sufixe_ (suffix trees^{'[1]':siruri-de-sufixe#bibliografie}^) 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 in general un numar de fii egal cu marimea alfabetului sirurilor de caractere care trebuies stocate. In cazul nostru, cu siruri ce contin litere mici ale alfabetului englez, fiecare nod va avea cel mult 26 de fii. Fiecare muchie porneste din tata spre fii si va fi etichetata cu o litera distincta a alfabetului. Etichetele legaturilor de pe un drum de la radacina pana la o frunza vor alcatui un cuvant stocat in arbore. Dupa cum se observa, verificarea existentei unui cuvant in aceasta structura de date este foarte eficienta si se realizeaza in complexitate $O(M)$, unde $M$ e lungimea cuvantului. Astfel, timpul de cautare nu depinde de numarul de cuvinte pe care trebuie sa il 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 incepe la pozitia $i$. Fie $n$ = lungimea lui $A$. Trie-ul de sufixe este format prin comprimarea tuturor sufixelor $A{~1~}...A{~n-1~}$ intr-un trie, ca in figura de mai jos. Trie-ul de sufixe corespunzator stringului $abac$ este:

* _verificarea daca un string $W$ este substring al lui $A$_ - este suficienta parcurgerea nodurilor, incepand 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 sfarsitului celor doua sufixe, iar prin aplicarea unui algoritm de gasire a LCA (Lowest Common Ancestor / cel mai apropiat stramos comun) se gaseste nodul corespunzator sfarsitului 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 in $O(sqrt(n))$, [3] pentru o prezentare accesibila a unei rezolvari in $O(log n)$ sau $O(1)$, si articolul [4] pentru un algoritm "state of the art".

* _cautarea celui mai lung prefix comun pentru doua sufixe ale lui $A$_ - se aleg nodurile $u$ si $v$ ale trie-ului corespunzatoare sfarsitului celor doua sufixe, iar prin aplicarea unui algoritm de gasire a LCA (Lowest Common Ancestor / cel mai apropiat stramos comun) se gaseste nodul corespunzator sfarsitului 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]':siruri-de-sufixe#bibliografie}^ pentru o rezolvare in $O(sqrt(n))$, '[3]':siruri-de-sufixe#bibliografie pentru o prezentare accesibila a unei rezolvari in $O(log n)$ sau $O(1)$, si articolul '[4]':siruri-de-sufixe#bibliografie pentru un algoritm "state of the art".

* _gasirea celui de-al $k$-lea sufix in ordine lexicografica_ - (complexitate $O(n)$, cu o preprocesare corespunzatoare). De exemplu al $3$-lea sufix al sirului $abac$ este reprezentat in trie-ul nostru de a $3$-a frunza.

Desi ideea unui trie de sufixe este incantatoare la prima vedere, implementarea simplista in care inseram pas cu pas sufixele in structura noastra necesita un timp de ordinul $O(n^2^)$. Exista o structura numita _arbore de sufixe_ [1] care se poate construi in timp liniar fata de lungimea sirului de caractere. Arborele de sufixe este un trie de sufixe in care lanturile din care nu ieseau alte muchii erau comprimate intr-o singura muchie (in exemplul de mai sus acestea ar fi lanturile $2-3-4-5$ si $1-7-8-9$). Dar implementarea  algoritmului de complexitate liniara pentru construirea unui arbore de sufixe este anevoioasa, fapt care ne determina sa cautam o alta structura, mai usor de realizat.

Desi ideea unui trie de sufixe este incantatoare la prima vedere, implementarea simplista in care inseram pas cu pas sufixele in structura noastra necesita un timp de ordinul $O(n^2^)$. Exista o structura numita _arbore de sufixe_^{'[1]':siruri-de-sufixe#bibliografie}^ care se poate construi in timp liniar fata de lungimea sirului de caractere. Arborele de sufixe este un trie de sufixe in care lanturile din care nu ieseau alte muchii erau comprimate intr-o singura muchie (in exemplul de mai sus acestea ar fi lanturile $2-3-4-5$ si $1-7-8-9$). Dar implementarea  algoritmului de complexitate liniara pentru construirea unui arbore de sufixe este anevoioasa, fapt care ne determina sa cautam o alta structura, mai usor de realizat.

Sa vedem care sunt sufixele lui $A$, parcurgind arborele in adancime. Avand in vedere faptul ca la parcurgerea in adancime trebuie sa consideram nodurile in ordinea lexicografic crescatoare a muchiilor care le leaga de tata, obtinem urmatorul sir de sufixe:

}
==

Complexitatea este insa $O(lg n)$ pentru un calcul al acestui prefix. Reducerea la $O(1)$ se bazeaza pe urmatoarea observatie: $lcp(x, y)$ = $min{ lcp(x, x + 1), lcp(x + 1, x + 2), ..., lcp(y - 1, y) }$. Demonstratia este imediata daca ne uitam in arborele de sufixe corespunzator. Asadar, este suficient ca la inceput sa calculam cel mai lung prefix comun intre toate perechile de sufixe consecutive (timp $O(n lg n)$) si sa introducem o structura aditionala ce permite calculul in $O(1)$ al minimului dintr-un interval. Cea mai eficienta astfel de structura este cea pentru RMQ (range minimum query), despre care nu vom da detalii aici, dar care este studiata in amanunt in [3], [4] si [5]. Cu inca o preprocesare in $O(n lg n)$ ceruta de noua structura putem acum sa raspundem in $O(1)$ query-urilor LCP. Structura folosita de RMQ cere tot $O(n lg n)$ memorie, asadar timpul si memoria finale necesare sunt $O(n lg n)$.

Complexitatea este insa $O(lg n)$ pentru un calcul al acestui prefix. Reducerea la $O(1)$ se bazeaza pe urmatoarea observatie: $lcp(x, y)$ = $min{ lcp(x, x + 1), lcp(x + 1, x + 2), ..., lcp(y - 1, y) }$. Demonstratia este imediata daca ne uitam in arborele de sufixe corespunzator. Asadar, este suficient ca la inceput sa calculam cel mai lung prefix comun intre toate perechile de sufixe consecutive (timp $O(n lg n)$) si sa introducem o structura aditionala ce permite calculul in $O(1)$ al minimului dintr-un interval. Cea mai eficienta astfel de structura este cea pentru RMQ (range minimum query), despre care nu vom da detalii aici, dar care este studiata in amanunt in '[3]':siruri-de-sufixe#bibliografie, '[4]':siruri-de-sufixe#bibliografie si '[5]':siruri-de-sufixe#bibliografie. Cu inca o preprocesare in $O(n lg n)$ ceruta de noua structura putem acum sa raspundem in $O(1)$ query-urilor LCP. Structura folosita de RMQ cere tot $O(n lg n)$ memorie, asadar timpul si memoria finale necesare sunt $O(n lg n)$.

h2(#cautare). 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.

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]':siruri-de-sufixe#bibliografie 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). Probleme de concurs

Daca ar fi vorba doar de doua siruri de lungimi mai mici am putea rezolva usor problema folosind metoda programarii dinamice; astfel, solutia pentru doua siruri ar avea ordinul de complexitate $O(N^2^)$.
O alta idee ar fi sa consideram fiecare sufix al sirului $S{~1~}$ si sa incercam sa ii gasim potrivirea de lungime maxima in celelalte doua siruri.

Potrivirea de lungime maxima rezolvata naiv ar avea complexitatea $O(N^2^)$, dar folosind algoritmul $KMP$ [8], putem obtine prefixul maxim al unui sir care se gaseste ca subsecventa in al doilea sir in $O(N)$, iar utilizand aceasta metoda pentru fiecare sufix al lui $S{~1~}$, am avea o solutie al carei ordin de complexitate este $O(N^2^)$.

Potrivirea de lungime maxima rezolvata naiv ar avea complexitatea $O(N^2^)$, dar folosind algoritmul $KMP$^{'[8]':siruri-de-sufixe#bibliografie}^, putem obtine prefixul maxim al unui sir care se gaseste ca subsecventa in al doilea sir in $O(N)$, iar utilizand aceasta metoda pentru fiecare sufix al lui $S{~1~}$, am avea o solutie al carei ordin de complexitate este $O(N^2^)$.

Sa vedem ce se intampla daca sortam sufixele celor trei siruri:
p=. !siruri-de-sufixe?fig08.png!

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

Cea mai mica valoare a lui $k$ pentru care distanta $d$ este suficient de mica reprezinta lungimea sablonului cautat (in cazul precedent $k = 5$). Pentru a obtine un algoritm de complexitate buna trebuie ca acest pas sa fie eficient; putem sa folosim un arbore de intervale, sa folosim un contor cu $k$ care variaza de la $1$ la $n$ si sa eliminam din arbore elemente de marime mai mica decat $k$ si, la fiecare pas, sa actualizam arborele pentru a putea raspunde la interogari de genul: _care este distanta maxima intre doua elemente care exista acum in structura_. Algoritmul are complexitatea $O(N log N)$. Pentru o prezentare amanuntita a arborilor de intervale, va recomand [9] si [10].

Cea mai mica valoare a lui $k$ pentru care distanta $d$ este suficient de mica reprezinta lungimea sablonului cautat (in cazul precedent $k = 5$). Pentru a obtine un algoritm de complexitate buna trebuie ca acest pas sa fie eficient; putem sa folosim un arbore de intervale, sa folosim un contor cu $k$ care variaza de la $1$ la $n$ si sa eliminam din arbore elemente de marime mai mica decat $k$ si, la fiecare pas, sa actualizam arborele pentru a putea raspunde la interogari de genul: _care este distanta maxima intre doua elemente care exista acum in structura_. Algoritmul are complexitatea $O(N log N)$. Pentru o prezentare amanuntita a arborilor de intervale, va recomand '[9]':siruri-de-sufixe#bibliografie si '[10]':siruri-de-sufixe#bibliografie.

h3. *Problema 9* (Olimpiada Baltica de Informatica, 2004)