h1. Siruri de sufixe

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

== include(page="template/implica-te/scrie-articole-2" user_id1="amadaeus" user_id2="Marius") ==

(Categoria _Algoritmi_, Autori _Adrian Vladu, Negruseri Cosmin_)

(Categoria _Structuri de date_, Autori _Adrian Vladu, Cosmin Negruseri_)

(toc){width: 25em}*{text-align:center;} *Continut*
* 'Introducere':siruri-de-sufixe#introducere

* _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]':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".

* _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]':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:

Sa vedem care sunt sufixele lui $A$, parcurgand 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:

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

sfarsit pentru
==

De remarcat ca nu este neparat necesara o anumita numerotare a substringurilor, atat timp cat intre ele este pastrata o relatie de ordine valida. In vederea atingerii complexitatii $O(n lg n)$ pentru sortare se recomanda folosirea metodei _radix sort_ (de doua ori sortare prin numarare), aceasta avand complexitate $O(n)$. Insa, pentru usurarea implementarii, se poate folosi functia $sort()$ din STL (Standard Template Library, o librarie ce contine unele structuri de date si algoritmi in limbajul C++). Desi complexitatea va creste la $O(n lg^2^ n)$ in cazul cel mai defavorabil, implementarea devine simtitor mai simpla, iar in practica diferentele sunt abia sesizabile pentru siruri cu lungime mai mica decat $100 000$.

De remarcat ca nu este neaparat necesara o anumita numerotare a substringurilor, atat timp cat intre ele este pastrata o relatie de ordine valida. In vederea atingerii complexitatii $O(n lg n)$ pentru sortare se recomanda folosirea metodei _radix sort_ (de doua ori sortare prin numarare), aceasta avand complexitate $O(n)$. Insa, pentru usurarea implementarii, se poate folosi functia $sort()$ din STL (Standard Template Library, o librarie ce contine unele structuri de date si algoritmi in limbajul C++). Desi complexitatea va creste la $O(n lg^2^ n)$ in cazul cel mai defavorabil, implementarea devine simtitor mai simpla, iar in practica diferentele sunt abia sesizabile pentru siruri cu lungime mai mica decat $100 000$.

Mai jos puteti vedea o implementare extrem de scurta pentru suffix array in $O(n lg^2^ n)$.

h3. *Problema 1*: '_Parola ascunsa_':https://www.spoj.pl/problems/BEADS/ (acm 2003, enunt modificat)

Consideram un sir de caractere de lungime $n$ $(1 ≤ n ≤ 100000)$. Sa se determine rotatia lui cilculara lexicografic minima. De exemplu, rotatiile sirului de caractere $alabala$ sunt:

Consideram un sir de caractere de lungime $n$ $(1 ≤ n ≤ 100000)$. Sa se determine rotatia lui circulara lexicografic minima. De exemplu, rotatiile sirului de caractere $alabala$ sunt:

$alabala$
$labalaa$
$abalaal$

Avand sufixele textului sortate, iteram cu o variabila $i$ de la $0$ la $N-K$ si calculam cel mai lung prefix comun intre sufixul $i$ si sufixul $i+K-1$. Prefixul maxim determinat in cursul acestei parcurgeri reprezinta solutia problemei.

h3. *Problema 4*: _Ghicit_ (baraj 2003)

h3. *Problema 4*: '_Ghicit_':http://infoarena.ro/problema/ghicit (baraj 2003)

Tu si cu Taranul jucati un joc neinteresant. Tu ai un sir de caractere mare. Taranul iti spune un alt sir de caractere, iar tu trebuie sa raspunzi cat mai repede daca sirul respectiv este sau nu o subsecventa a sirului tau.
Taranul  iti pune multe intrebari si, fiindca esti informatician, te-ai gandit ca ar merge mai repede daca ai sti dinainte toate sirurile despre care te poate intreba.

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)

h3. *Problema 9* (Olimpiada Baltica de Informatica^{%{font-size:12px}'[11]':siruri-de-sufixe#bibliografie%}^, 2004)

Un sir de caractere $S$ se numeste repetitie $(K, L)$ daca $S$ se obtine prin concatenarea de $K ≥ 1$ ori a unui sir $T$ de lungime $L ≥ 1$. De exemplu, sirul $S = abaabaabaaba$ este o repetitie $(4, 3)$ cu $T = aba$. Sirul $T$ are lungimea trei si $S$ se obtine repetandu-l pe $T$ de patru ori. Avand un sir de caractere $U$ format din caractere $a$ si/sau $b$ de lungime $n$ $(1 ≤ n ≤ 50000)$, va trebui sa determinati o repetitie $(K, L)$ care apare ca subsecventa a lui $U$ astfel incat $K$ sa fie cat mai mare. De exemplu, sirul $U = babbabaabaabaabab$ contine repetitia $(4, 3)$, sirul $S$ incepand de pe pozitia $5$. Aceasta este si repetitia maxima, deoarece sirul nu mai contine nici o alta subsecventa care sa se repete de mai mult de patru ori. Daca sirul contine mai multe solutii cu acelasi $K$, poate fi aleasa oricare dintre ele.

$*a* a b a a b$
$ a b a a b a a b a a b a *a b a*$

Extinzand in acest mod cat mai mult in stanga secventa noastra si apoi extinzand la dreapta prefixul de lungime $L$ (in exemplul nostru prefixul de lungime $3$) al secventei obtinute, gasim cea mai lunga repetitie a unui sir de caractere de lungime $L$ cu proprietatea ca repetitia contine ca subsecventa sirul $X$ (daca repetitia este $(1, L)$ afirmatia anterioara nu este adevarata, dar acesta este un caz trivial). Acum observam ca pentru a identifica toate repetitiile $(K, L)$ cu $L$ fixat din sirul $U$, este suficient sa partitionam sirul in $n/L$ bucati si sa extindem aceste bucati. Remarcam ca daca va fi posibil sa realizam acest lucru pentru ficare bucata in $O(1)$ algoritmul final va avea ordinul de complexitate $O(n/1 + n/2 + n/3 + .. + n/n)$ (fiecare bucata se poate repeta in totalitate sau doar partial in stanga sau in dreapta, iar noi nu vom extinde fiecare bucata separat, ci bucatile adiacente le vom reuni intr-o noua bucata; asadar, daca avem $p$ bucati consecutine de aceeasi dimensiune, vom determina extinderile lor maxime in timp $O(p)$). Dar stim ca sirul $1 + 1/2 + 1/3 + 1/4 + .. + 1/n - ln n$ converge spre o constanta $c$, numita constanta lui $Euler$, si $c < 1$; de aici tragem concluzia ca $O(n/1 + n/2 + n/3 + .. + n/n)$ = $O(log n)$, deci algoritmul, in cazul in care extinderile maxime pot fi calculate usor, ar avea ordinul de complexitate $O(n log n)$. Acum intervin in rezolvarea noastra arborii de sufixe. Pentru a determina cu cat putem extinde cel mai mult subsecventa $U[i..j]$ a sirului $U$ la dreapta, practic ne intereseaza cel mai lung prefix comun al subsecventei $U[i..j]$ si al subsecventei $U[j+1..n]$. Pentru a extinde cat mai mult la stanga este suficient sa inversam sirul $U$ si ajungem sa rezolvam aceeasi problema. Am vazut ca problema celui mai lung prefix comun a doua secvente se rezolva in timp $O(1)$ cu ajutorul sirurilor de sufixe. Astfel, avem nevoie de crearea sirului de sufixe, etapa pe care o rezolvam intr-un timp de ordinul $O(n log n)$ si apoi de aplicarea algoritmului explicat anterior care are complexitatea $O(n log n)$. In concluzie, algoritmul prezent are complexitatea totala $O(n log n)$.

Extinzand in acest mod cat mai mult in stanga secventa noastra si apoi extinzand la dreapta prefixul de lungime $L$ (in exemplul nostru prefixul de lungime $3$) al secventei obtinute, gasim cea mai lunga repetitie a unui sir de caractere de lungime $L$ cu proprietatea ca repetitia contine ca subsecventa sirul $X$ (daca repetitia este $(1, L)$ afirmatia anterioara nu este adevarata, dar acesta este un caz trivial). Acum observam ca pentru a identifica toate repetitiile $(K, L)$ cu $L$ fixat din sirul $U$, este suficient sa partitionam sirul in $n/L$ bucati si sa extindem aceste bucati. Remarcam ca daca va fi posibil sa realizam acest lucru pentru ficare bucata in $O(1)$ algoritmul final va avea ordinul de complexitate $O(n/1 + n/2 + n/3 + .. + n/n)$ (fiecare bucata se poate repeta in totalitate sau doar partial in stanga sau in dreapta, iar noi nu vom extinde fiecare bucata separat, ci bucatile adiacente le vom reuni intr-o noua bucata; asadar, daca avem $p$ bucati consecutine de aceeasi dimensiune, vom determina extinderile lor maxime in timp $O(p)$). Dar stim ca sirul $1 + 1/2 + 1/3 + 1/4 + .. + 1/n - ln n$ converge spre o constanta $c$, numita constanta lui $Euler$, si $c < 1$; de aici tragem concluzia ca $O(n/1 + n/2 + n/3 + .. + n/n)$ = $O(n log n)$, deci algoritmul, in cazul in care extinderile maxime pot fi calculate usor, ar avea ordinul de complexitate $O(n log n)$. Acum intervin in rezolvarea noastra arborii de sufixe. Pentru a determina cu cat putem extinde cel mai mult subsecventa $U[i..j]$ a sirului $U$ la dreapta, practic ne intereseaza cel mai lung prefix comun al subsecventei $U[i..j]$ si al subsecventei $U[j+1..n]$. Pentru a extinde cat mai mult la stanga este suficient sa inversam sirul $U$ si ajungem sa rezolvam aceeasi problema. Am vazut ca problema celui mai lung prefix comun a doua secvente se rezolva in timp $O(1)$ cu ajutorul sirurilor de sufixe. Astfel, avem nevoie de crearea sirului de sufixe, etapa pe care o rezolvam intr-un timp de ordinul $O(n log n)$ si apoi de aplicarea algoritmului explicat anterior care are complexitatea $O(n log n)$. In concluzie, algoritmul prezent are complexitatea totala $O(n log n)$.

h3. *Problema 10* (ACM SEER 2004)

# Mark Nelson, _Fast string searching with suffix trees_
# Mircea Pasoi, '_Multe "smenuri" de programare in C/C++... si nu numai!_':multe-smenuri-de-programare-in-cc-si-nu-numai

# Emilian Miron, '_LCA - Lowest common ancestor_':lca-lowest-common-ancestor

# Emilian Miron, '_LCA - Lowest common ancestor_':lowest-common-ancestor

# Michael A. Bender, Martin Farach-Colton, _The LCA Problem Revisited_
# Erik Demaine, _MIT Advanced Data Structures, Lecture 11, April 2nd, 2003_
# Udi Manber, Gene Myers, '_Suffix arrays: A new method for on-line string searches_':http://webglimpse.net/pubs/suffix.pdf

3691