Diferente pentru siruri-de-sufixe intre reviziile #24 si #54

Nu exista diferente intre titluri.

Diferente intre continut:

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_)
h2. Introducere
(toc){width: 25em}*{text-align:center;} *Continut*
* 'Introducere':siruri-de-sufixe#introducere
* 'Ce sunt sirurile de sufixe (suffix arrays)?':siruri-de-sufixe#prezentare
* 'Cum construim un sir de sufixe?':siruri-de-sufixe#constructie
* 'Calcularea celui mai lung prefix comun @(LCP)@':siruri-de-sufixe#lcp
* 'Cautarea':siruri-de-sufixe#cautare
* 'Probleme de concurs':siruri-de-sufixe#probleme
* 'Concluzii':siruri-de-sufixe#concluzii
* 'Bibliografie':siruri-de-sufixe#bibliografie
Un domeniu important in algoritmica folosita in practica este acela al algoritmilor pe siruri de caractere. Astfel la concursurile de programare sunt prezente foarte multe probleme de prelucrare si procesare a unor siruri de caractere. In cadrul concursurilor si antrenamentelor multi dintre noi s-au lovit de probleme ce s-ar fi rezolvat usor daca se reusea in mod eficient determinarea existentei unui cuvant ca subsecventa a unui alt cuvant. Vom prezenta o structura versatila ce permite acest lucru, inlesnind de multe ori realizarea altor operatii utile pe un string dat.
h2(#introducere). Introducere
h2. Ce sunt sirurile de sufixe (suffix arrays)?
Un domeniu important in algoritmica folosita in practica este acela al algoritmilor pe siruri de caractere. Astfel, la concursurile de programare sunt prezente foarte multe probleme de prelucrare si procesare a unor siruri de caractere. In cadrul concursurilor si antrenamentelor multi dintre noi s-au lovit de probleme ce s-ar fi rezolvat usor daca se reusea in mod eficient determinarea existentei unui cuvant ca subsecventa a unui alt cuvant. Vom prezenta o structura versatila ce permite acest lucru, inlesnind de multe ori realizarea altor operatii utile pe un string dat.
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 care 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, cautarea 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.
h2(#prezentare). Ce sunt sirurile de sufixe (suffix arrays)?
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:
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:
p=. !siruri-de-sufixe?fig01v.png!
* _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 prefixe, iar prin aplicarea unui algoritm de gasire a LCA (least 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:
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!
Este usor de observat ca acestea sunt ordonate crescator. Pentru memorare, nu este necesar sa pastram un vector ordonat de sufixe, suficienta fiind pastrarea indicilor fiecarui sufix din sirul ordonat. Pentru exemplul de mai sus obtinem vectorul *$P = (0, 2, 1, 3)$*, acesta fiind array-ul de sufixe pentru stringul $abac$.
Este usor de observat ca acestea sunt ordonate crescator. Pentru memorare, nu este necesar sa pastram un vector ordonat de sufixe, suficienta fiind pastrarea indicilor fiecarui sufix din sirul ordonat. Pentru exemplul de mai sus obtinem vectorul $P = (0, 2, 1, 3)$, acesta fiind array-ul de sufixe pentru stringul $abac$.
h2. Cum construim un sir de sufixe (suffix array)?
h2(#constructie). Cum construim un sir de sufixe?
Prima metoda care ne vine in minte este sortarea tuturor sufixelor lui $A$ folosind un algoritm de complexitate $O(n lg n)$. Insa compararea a doua sufixe se face in timp $O(n)$, deci complexitatea finala va fi $O(n^2^ lg n)$. Exista totusi un algoritm relativ usor de implementat si inteles, avand o complexitate de $O(n lg n)$. Desi este asimptotic mai mare decat cel al constructiei unui arbore de sufixe (suffix tree), in practica timpul de constructie al unui sir de sufixe este mult mai mic, din cauza constantei care apare in fata algoritmul liniar. De asemenea, cantitatea de memorie folosita in cazul implementarii cu memorie $O(n)$ este de la $3$ pana la $5$ ori mai mica decat in cazul unui arbore de sufixe.
Prima metoda care ne vine in minte este sortarea tuturor sufixelor lui $A$ folosind un algoritm de complexitate $O(n lg n)$. Insa compararea a doua sufixe se face in timp $O(n)$, deci complexitatea finala va fi $O(n^2^ lg n)$. Exista totusi un algoritm relativ usor de implementat si inteles, avand o complexitate de $O(n lg n)$. Desi este asimptotic mai mare decat cel al constructiei unui arbore de sufixe (suffix tree), in practica timpul de constructie al unui sir de sufixe este mult mai mic, din cauza constantei care apare in fata algoritmul liniar. De asemenea, cantitatea de memorie folosita in cazul implementarii cu memorie $O(n)$ este de la 3 pana la 5 ori mai mica decat in cazul unui arbore de sufixe.
Algoritmul se bazeaza pe mentinerea ordinii sufixelor sirului, sortate dupa prefixele lor de lungime $2^k^$. Astfel vom executa $m$ = $[log{~2~}n]$ (marginit superior) pasi, la pasul $k$ stabilind ordinea sufixelor daca sunt luate in considerare doar primele $2^k^$ caractere din fiecare sufix. Se foloseste o matrice $P$ de dimensiune $m x n$.  Notam cu $A{~i~}^k^$ subsecventa lui $A$ de lungime $2^k^$ ce incepe pe pozitia $i$. Pozitia lui $A{~i~}^k^$ in sirul sortat al subsecventelor $A{~j~}^k^$ $(j=1,n)$ se pastreaza in $P{~(k,i)~}$.
Algoritmul se bazeaza pe mentinerea ordinii sufixelor sirului, sortate dupa prefixele lor de lungime $2^k^$. Astfel vom executa $m$ = $[log{~2~}n]$ (marginit superior) pasi, la pasul $k$ stabilind ordinea sufixelor daca sunt luate in considerare doar primele $2^k^$ caractere din fiecare sufix. Se foloseste o matrice $P$ de dimensiune $m x n$.  Notam cu $A{~i~}^k^$ subsecventa lui $A$ de lungime $2^k^$ ce incepe pe pozitia $i$. Pozitia lui $A{~i~}^k^$ in sirul sortat al subsecventelor $A{~j~}^k^$ $(j=0,n-1)$ se pastreaza in $P{~(k,i)~}$.
Pentru a trece de la pasul $k$ la pasul $k+1$ se concateneaza toate secventele $A{~i~}^k^$ cu $A{~i+2^k^~}^ k^$, obtinandu-se astfel substringurile de lungime $2^k+1^$. Pentru stabilirea ordinii se folosesc informatiile obtinute la pasul anterior. Pentru fiecare indice $i$ se pastreaza o pereche de intregi formata din $P{~(k,i)~}$ si $P{~(k,i+2^k^)~}$. Nu trebuie sa ne preocupe faptul ca $i+2^k^$ poate pica in afara sirului, deoarece vom completa sirul cu pseudocaracterul {@$@}, despre care vom considera ca este lexicografic mai mic decat oricare alt caracter. In urma sortarii, perechile vor fi aranjate conform ordinii lexicografice a substringurilor de lungime $2^k+1^$ corespunzatoare. Un ultim lucru care mai trebuie notat este ca la un anumit pas $k$, pot exista doua (sau mai multe) substringuri $A{~i~}^k^$ = $A{~j~}^k^$, iar acestea trebuie etichetate identic ({$P{~(k,i)~}$} trebuie sa fie egal cu {$P{~(k,j)~}$}). O imagine spune mai mult decat o mie de cuvinte:
p=. !siruri-de-sufixe?fig02.png!
*Pasul 0*:
Pasul 0:
p=. !siruri-de-sufixe?fig03.png!
*Pasul 1*:
Pasul 1:
p=. !siruri-de-sufixe?fig04.png!
*Pasul 2*:
Pasul 2:
p=. !siruri-de-sufixe?fig05.png!
*Pasul 3*:
Pasul 3:
p=. !siruri-de-sufixe?fig06.png!
== code(c) |
n <- lungime(A)
pentru i <- 0, n-1
	P(0, i) <- pozitia lui Ai in sirul ordonat al caracterelor lui A
    P(0, i) <- pozitia lui Ai in sirul ordonat al caracterelor lui A
sfarsit pentru
cnt <- 1
pentru k <- 1, [log2 n] (marginit superior)
	pentru i <- 0, n-1
		L(i) <- (P(k-1, i), P(k-1, i+cnt), i)
        sfarsit pentru
	sorteaza L
	calculeaza P(k, i), i = 0, n-1
	cnt <- 2 * cnt
    pentru i <- 0, n-1
        L(i) <- (P(k-1, i), P(k-1, i+cnt), i)
    sfarsit pentru
    sorteaza L
    calculeaza P(k, i), i = 0, n-1
    cnt <- 2 * cnt
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)$.
#include <cstdio>
#include <cstring>
#include <algorithm>
 
using namespace std;
#define MAXN  65536
#define MAXLG 17
const int MAXN = 65536;
const int MAXLG = 17;
char A[MAXN];
struct entry {
} L[MAXN];
int P[MAXLG][MAXN], N, i, stp, cnt;
int cmp(struct entry a, struct entry b)
{
    return a.nr[0] == b.nr[0] ? (a.nr[1] < b.nr[1] ? 1 : 0) : (a.nr[0] < b.nr[0] ? 1 : 0);
bool cmp(const entry &a, const entry &b) {
    return a.nr[0] == b.nr[0] ? (a.nr[1] < b.nr[1]) : (a.nr[0] < b.nr[0]);
}
int main(void)
{
int main() {
    gets(A);
    for (N = strlen(A), i = 0; i < N; i ++)
    for (N = strlen(A), i = 0; i < N; ++i)
        P[0][i] = A[i] - 'a';
    for (stp = 1, cnt = 1; cnt >> 1 < N; stp ++, cnt <<= 1)
    {
        for (i = 0; i < N; i ++)
        {
    for (stp = 1, cnt = 1; cnt >> 1 < N; ++stp, cnt <<= 1) {
        for (i = 0; i < N; ++i) {
            L[i].nr[0] = P[stp - 1][i];
            L[i].nr[1] = i + cnt < N ? P[stp - 1][i + cnt] : -1;
            L[i].p = i;
        }
        sort(L, L + N, cmp);
        for (i = 0; i < N; i ++)
        for (i = 0; i < N; ++i)
            P[stp][L[i].p] = i > 0 && L[i].nr[0] == L[i - 1].nr[0] && L[i].nr[1] == L[i - 1].nr[1] ? P[stp][L[i - 1].p] : i;
    }
    return 0;
Sirul de sufixe se va gasi pe ultima linie a matricei $P$. Cautarea celui de-al $k$-lea sufix in ordine lexicografica este acum imediata, deci nu vom reveni asupra acestui aspect.
Cantitatea de memorie folosita poate fi redusa renuntand la folosirea intregii matrice $P$ si pastrindu-se la fiecare pas doar ultimele doua linii ale acesteia. In acest caz, insa, structura nu va mai fi capabila sa execute eficient operatia ce urmeaza.
h2. Calcularea celui mai lung prefix comun (LCP)
h2(#lcp). Calcularea celui mai lung prefix comun (LCP)
Se dau doua sufixe ale unui string $A$. Se cere calcularea celui mai lung prefix comun al lor. Am aratat ca un arbore de sufixe poate realiza aceasta in timp $O(1)$ cu o preprocesare corespunzatoare. Sa vedem daca un sir de sufixe poate atinge aceeasi performanta.
Fie cele doua sufixe $A{~i~}$ si $A{~j~}$. Folosind matricea $P$, putem itera descrescator de la cel mai mare $k$ pana la $0$ si verifica daca $A{~i~}^k^$ = $A{~j~}^k^$. Daca cele doua prefixe sunt egale, am gasit un prefix comun de lungime $2^k^$. Nu ne ramane decat sa actualizam $i$ si $j$, incrementandu-le cu $2^k^$ si sa verificam in continuare daca mai gasim prefixe comune.
Codul functiei care calculeaza _LCP_ este foarte simplu:
Fie cele doua sufixe $A{~i~}$ si $A{~j~}$. Folosind matricea $P$, putem itera descrescator de la cel mai mare $k$ pana la $0$ si verifica daca $A{~i~}^k^$ = $A{~j~}^k^$. Daca cele doua prefixe sunt egale, am gasit un prefix comun de lungime $2^k^$. Nu ne ramane decat sa actualizam $i$ si $j$, incrementandu-le cu $2^k^$ si sa verificam in continuare daca mai gasim prefixe comune. Codul functiei care calculeaza LCP este foarte simplu:
== code(cpp) |
int lcp(int x, int y)
{
int lcp(int x, int y) {
    int k, ret = 0;
    if (x == y) return N - x;
    for (k = stp - 1; k >= 0 && x < N && y < N; k --)
    for (k = stp - 1; k >= 0 && x < N && y < N; --k)
        if (P[k][x] == P[k][y])
            x += 1 << k, y += 1 << k, ret += 1 << k;
    return ret;
}
==
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. Cautarea
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 de concurs
h2(#probleme). Probleme de concurs
Autorii au incercat sa adune cat mai multe probleme ce pot fi rezolvate cu ajutorul sirurilor de sufixe. Parcurgerea tuturor problemelor la prima citire, ar putea fi greoaie pentru un cititor care a avut primul contact cu aceasta structura de date citind acest articol. Pentru a usura lectura problemele sunt asezate intr-o ordine crescatoare a dificultatilor.
h3. *Problema 1*: _Parola ascunsa_ (acm 2003, enunt modificat)
h3. *Problema 1*: '_Parola ascunsa_':https://www.spoj.pl/problems/BEADS/ (acm 2003, enunt modificat)
Consideram un sir de caractere de lungime $n$ $(1 &le; n &le; 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 &le; n &le; 100000)$. Sa se determine rotatia lui circulara lexicografic minima. De exemplu, rotatiile sirului de caractere $alabala$ sunt:
$alabala$
$labalaa$
$abalaal$
Sirul cautat este prima permutare circulara in ordine lexicografica a sirului dat. Notam cu $S{~i~}^k^$ substringul de lungime $k$ ce incepe la pozitia $i$. Fie $S{~i~}^n^$ cel mai mic substring in ordine lexicografica de lungime $n$ al sirului obtinut prin concatenare.  Presupunand prin absurd ca $s(i+n-1) < n$ ar insemna ca exista un $i'$ $(i < i' &le; j)$ astfel incat $S{~i'~}^j-i'+1^$ este lexicografic mai mic decat $S{~i~}^n^$. Dar din conditia impusa de enunt avem $S{~i'~}^j-i'+1^ > S{~i'~}^n^$. Dar $S{~i'~}^n^ > S{~i~}^n^$ => contradictie.
Desi exista un algorirm de complexitate $O(n)$ specializat pentru siruri ce contin doar literele $A$ si $B$, metoda preferata de autor (si cu care a obtinut punctaj maxim in timpul concursului) a fost folosirea sirurilor de sufixe, ca in problema anterioara.
h3. *Problema 3*: _Substr_ (baraj 2003)
h3. *Problema 3*: '_Substr_':http://infoarena.ro/problema/substr (baraj 2003)
Se da un text format din $N$ caractere (litere mari, litere mici si cifre). Un substring al acestui text este o secventa de caractere care apar pe pozitii consecutive in text. Fiind dat un numar $K$, sa se gaseasca lungimea celui mai lung substring care apare in text de cel putin $K$ ori $(1 &le; N &le; 16384)$.
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.
h3. Solutie:
Aceasta problema ne cere, de fapt, sa calculam numarul de noduri (fara radacina) ale trie-ului de sufixe asociat unui string. Fiecare secventa distincta din sir este determinata de drumul unic pe care il parcurgem in trie-ul de sufixe cand cautam acea secventa. Pentru exemplul $abac$ avem secventele $a$, $ab$, $aba$, $abac$, $ac$, $b$, $ba$, $bac$ si $c$, acestea sunt determinate  de drumul de la radacina trieului spre nodurile $2$, $3$, $4$, $5$, $6$, $7$, $8$ si $9$ in aceasta ordine. Cum constructia trie-ului de sufixe are complexitate patratica, iar construirea unui arbore de sufixe este anevoioasa, este preferabila o abordare prin prisma sirurilor de sufixe. Obtinem sirul sortat de sufixe in $O(n lg n)$, dupa care cautam pozitia in care fiecare pereche de sufixe consecutive difera (folosind functia $lcp$) si adunam la solutie restul caracterelor. Complexitatea totala este $O(n lg n)$.
Aceasta problema ne cere, de fapt, sa calculam numarul de noduri (fara radacina) ale trie-ului de sufixe asociat unui string. Fiecare secventa distincta din sir este determinata de drumul unic pe care il parcurgem in trie-ul de sufixe cand cautam acea secventa. Pentru exemplul $abac$ avem secventele $a$, $ab$, $aba$, $abac$, $ac$, $b$, $ba$, $bac$ si $c$, acestea sunt determinate de drumul de la radacina trieului spre nodurile $2$, $3$, $4$, $5$, $6$, $7$, $8$ si $9$ in aceasta ordine. Cum constructia trie-ului de sufixe are complexitate patratica, iar construirea unui arbore de sufixe este anevoioasa, este preferabila o abordare prin prisma sirurilor de sufixe. Obtinem sirul sortat de sufixe in $O(n lg n)$, dupa care cautam pozitia in care fiecare pereche de sufixe consecutive difera (folosind functia $lcp$) si adunam la solutie restul caracterelor. Complexitatea totala este $O(n lg n)$.
h3. *Problema 5*: _SETI_ (ONI 2002, enunt modificat)
h3. *Problema 5*: '_SETI_':http://infoarena.ro/problema/seti (ONI 2002, enunt modificat)
Se da un string de lungime $N$ $(1 &le; N &le; 131072)$ si $M$ stringuri de lungime cel mult $64$. Se cere sa se numere aparitiile fiecarui string din cele $M$ in stringul mare.
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:
$a&sect;$
$abababca&sect;$
$ababca&sect;$
$abca&sect;$
$bababca&sect;$
$babca&sect;$
$bca&sect;$
$ca&sect;$
$aababc#$
$ababc#$
$abc#$
$babc#$
$bc#$
$c#$
$a@$
$aaababca@$
$aababca@$
$ababca@$
$abca@$
$babca@$
$bca@$
$ca@$
p=. !siruri-de-sufixe?fig08.png!
Acum interclasam prefixele celor trei siruri (consideram $&sect; < # < @ < a ...)$:
$a&sect;$
$a@$
$aaababca@$
$aababc#$
$aababca@$
$abababca&sect;$
$ababc#$
$ababca&sect;$
$ababca@$
$abc#$
$abca&sect;$
$abca@$
$bababca&sect;$
$babc#$
$babca&sect;$
$babca@$
$bc@$
$bca&sect;$
$bca@$
$c@$
$ca&sect;$
$ca@$
p=. !siruri-de-sufixe?fig09.png!
Subsecventa comuna maxima corespunde prefixelor comune maxime pentru cele trei sufixe $ababca&sect;$, $ababc#$ si $ababca@$. Urmariti unde apar ele in sirul sortat al tuturor sufixelor. De aici avem ideea ca solutia se afla ca o secventa $i..j$ a sirului sortat de sufixe cu proprietatea ca secventa contine cel putin cate un sufix din fiecare sir, iar prefixul cel mai lung comun primului sufix din secventa si ultimul sufix din secventa este maxim; acest cel mai lung prefix este chiar solutia problemei. Alte subsecvente comune ale celor trei siruri ar fi prefixe comune pentru cate o subsecventa a sirului de sufixe sortat, de exemplu $bab$ pentru $bababca&sect;$, $babc@$, $babca&sect;$, sau $a$ pentru $a&sect;$, $a@$, $aaababca@$, $aababc#$. Pentru a determina aceasta secventa de prefix comun maxim putem folosi o parcurgere cu doi indici ({$start$} si $end$). Indicele $start$ variaza intre $1$ si numarul de sufixe, iar $end$ este cel mai mic indice mai mare decat $start$ astfel incat intre $start$ si $end$ sa existe sufixe din toate cele trei siruri. Astfel, perechea $[start, end]$ va indica, la un moment dat, secventa optima $[i..j]$. Aceasta parcurgere este liniara, deoarece $start$ poate avea cel mult $n$ valori, iar $end$ va fi incrementat de cel mult $n$ ori. Pentru a sorta sirul tuturor sufixelor nu este nevoie sa sortam mai intai sufixele fiecarui sir si apoi sa interclasam sufixele. Putem realiza operatia mult mai simplu concatenand cele trei siruri in unul singur (pentru exemplul considerat avem $abababca&sect;aababc@aaababca#)$ si sortand sufixele acestuia.
Subsecventa comuna maxima corespunde prefixelor comune maxime pentru cele trei sufixe $ababca&sect;$, $ababc#$ si $ababca@$. Urmariti unde apar ele in sirul sortat al tuturor sufixelor. De aici avem ideea ca solutia se afla ca o secventa $[i..j]$ a sirului sortat de sufixe cu proprietatea ca secventa contine cel putin cate un sufix din fiecare sir, iar prefixul cel mai lung comun primului sufix din secventa si ultimul sufix din secventa este maxim; acest cel mai lung prefix este chiar solutia problemei. Alte subsecvente comune ale celor trei siruri ar fi prefixe comune pentru cate o subsecventa a sirului de sufixe sortat, de exemplu $bab$ pentru $bababca&sect;$, $babc@$, $babca&sect;$, sau $a$ pentru $a&sect;$, $a@$, $aaababca@$, $aababc#$. Pentru a determina aceasta secventa de prefix comun maxim putem folosi o parcurgere cu doi indici ({$start$} si $end$). Indicele $start$ variaza intre $1$ si numarul de sufixe, iar $end$ este cel mai mic indice mai mare decat $start$ astfel incat intre $start$ si $end$ sa existe sufixe din toate cele trei siruri. Astfel, perechea $[start, end]$ va indica, la un moment dat, secventa optima $[i..j]$. Aceasta parcurgere este liniara, deoarece $start$ poate avea cel mult $n$ valori, iar $end$ va fi incrementat de cel mult $n$ ori. Pentru a sorta sirul tuturor sufixelor nu este nevoie sa sortam mai intai sufixele fiecarui sir si apoi sa interclasam sufixele. Putem realiza operatia mult mai simplu concatenand cele trei siruri in unul singur (pentru exemplul considerat avem $abababca&sect;aababc@aaababca#)$ si sortand sufixele acestuia.
h3. *Problema 7*: _Cel mai lung palindrom_ (USACO Training Gate)
h3. Solutie:
Daca dorim sa determinam, pentru un indice fixat $i$, care este cel mai mare palindrom centrat in $i$ atunci ne intereseaza prefixul maxim al subsecventei $S[i+1..n]$ care se potriveste cu prefixul subsecventei $S[1..i]$ reflectate. Pentru a rezolva cu usurinta aceasta problema sortam impreuna si sufixele sirului cu prefixele reflectate ale sirului (operatie care se realizeaza usor concatenand sirul $S&sect;$ cu sirul $S$ oglindit $S^'^$) si vom efectua interogari pentru cel mai lung prefix comun pentru $S[i+1]$ si $S^'^[n-i+1]$ $(S^'^[n-i+1] = S[1..i])$, la care putem raspunde folosind siruri de sufixe in timp $O(1)$. Astfel, putem rezolva problema in timp $O(N log N)$. Sa observam ca am tratat aici doar cazul in care palindromul este de lungime para, dar cazul in care palindromul are lungime impara se trateaza analog.
Daca dorim sa determinam, pentru un indice fixat $i$, care este cel mai mare palindrom centrat in $i$ atunci ne intereseaza prefixul maxim al subsecventei $S[i+1..n]$ care se potriveste cu prefixul subsecventei $S[1..i]$ reflectate. Pentru a rezolva cu usurinta aceasta problema sortam impreuna si sufixele sirului cu prefixele reflectate ale sirului (operatie care se realizeaza usor concatenand sirul $S&sect;$ cu sirul $S$ oglindit, $S^'^$) si vom efectua interogari pentru cel mai lung prefix comun pentru $S[i+1]$ si $S^'^[n-i+1]$ $(S^'^[n-i+1] = S[1..i])$, la care putem raspunde folosind siruri de sufixe in timp $O(1)$. Astfel, putem rezolva problema in timp $O(N log N)$. Sa observam ca am tratat aici doar cazul in care palindromul este de lungime para, dar cazul in care palindromul are lungime impara se trateaza analog.
h3. *Problema 8*: _Template_ (Olimpiada poloneza 2004, enunt modificat)
$7: baab$
$8: baabaab$
$A = a b a a b a a b &sect;$
p=. !siruri-de-sufixe?fig12.png!
 
h3. Solutia 2 (Mircea Pasoi):
 
Pentru sirul de caractere $S$, determinam pentru fiecare $i$ de la $1$ la $n$ lungimea celui mai lung prefix al lui $S$ cu $S[i..n]$. Aceasta operatie se poate realiza folosind siruri de sufixe. De exemplu, daca $S$ este sirul nostru si $T$ este sirul de potriviri maxime ale sufixelor, atunci:
 
p=. !siruri-de-sufixe?fig10.png!
 
Pentru toate lungimile posibile $k$ ale sablonului $(1 &le; k &le; n)$ verificam daca distanta maxima $d$ intre indicii celor mai departate doua elemente de valori mai mari sau egale cu $k$ in sirul $T$ nu este mai mare decat $k$. Prezentam in continuare un exemplu:
 
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]':siruri-de-sufixe#bibliografie si '[10]':siruri-de-sufixe#bibliografie.
 
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 &ge; 1$ ori a unui sir $T$ de lungime $L &ge; 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 &le; n &le; 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.
$1) B = a  => S = 1 0 1 1 0 1 1 0 1; L = 1, R = 5, distanta maxima = 2;$
h3. Solutie:
 
Dorim ca pentru un $L$ fixat sa determinam cea mai mare valoare $K$ astfel incat in sirul $U$ sa avem o subsecventa $S$ care este repetitie $(K, L)$. Vom considera acum un exemplu: $U = babaabaabaabaaab$, $L = 3$ si o subsecventa fixata $X = aab$ care incepe pe pozitia $4$ a sirului $U$. Putem incerca sa extindem secventa $aab$ la ambele capete cat mai mult posibil prin repetarea ei asa cum vedem in continuare:
 
$b a b *a a b* a a b a a b a a a b$
$*a* a b a a b$
$&emsp;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 &lt; 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)
$2) B = a b  => S = 1 0 0 1 0 0 1 0 1; L = 3, R = 5, distanta maxima = 3;$
Avand un sir de caractere $S$ dat, se cere ca pentru fiecare prefix al sau sa se determine daca este un sir de caractere periodic. Astfel, pentru fiecare $i$ $(2 &le; i &le; N)$ ne intereseaza cel mai mare $K &ge; 1$ (daca exista un asemenea $K$) cu proprietatea ca prefixul lui $S$ de lungime $i$ poate fi scris cub forma $A^k^$ (sirul $A$ concatenat cu el insusi de $k$ ori) pentru un sir de caractere $A$. De asemenea, ne intereseaza si valoarea $k$ (avem $0 &le; N &le; 1000000$).
$3) B = a b a  => S = 1 0 0 1 0 0 0 0 1; L = 4, R = 5, distanta maxima = 5;$
h4. Exemplu
 
Pentru sirul $aabaabaabaab$ obtinem rezultatul prezentat in continuare:
 
$2 2$
$6 2$
$9 3$
$12 4$
 
h4. Explicatii
 
* prefixul $aa$ are perioada $a$;
* prefixul $aabaab$ are perioada $aab$;
* prefixul $aabaabaab$ are perioada $aab$;
* prefixul $aabaabaabaab$ are perioada $aab$;
 
h3. Solutie:
$4) B = a b a a  => S = 1 0 0 1 0 0 0 0 1; L = 4, R = 5, distanta maxima = 5;$
Sa vedem ce se intampla cand incercam sa potrivim un sir cu un sufix al sau. Consideram un sir si il impartim in doua, obtinand un prefix si un sufix:
$5) B = a b a a b  => S = 1 0 0 1 0 0 0 0 1; L = 4, R = 5, distanta maxima = 5;$
$S = aab aabaabaaaab$
$suf = aab aabaaaab$
$pre = aab$
 
Daca sufixul se potriveste cu sirul initial pe un numar de caractere mai mare sau egal cu lungimea sirului $pre$, inseamna ca $pre$ este si un prefix al sufixului; deducem ca putem imparti si sufixul in $pre$ si $suf1$, iar sirul putem sa il impartim in $pre$, $pre$ si $suf1$. Daca sirul se potriveste cu sufixul pe un numar de caractere mai mare sau egal cu dublul lungimii sirului $pre$, atunci sufixul se potriveste cu $suf1$ pe un numar de caractere mai mare sau egal cu lungimea sirului $pre$, deci $suf1$ poate fi scris ca $pre$ si $suf2$, deci $suf$ poate fi scris ca $pre$, $pre$, $suf2$, iar $S$ poate fi scris ca $pre$, $pre$, $pre$, $suf2$:
 
$S = aab aab aab aaaab$
$suf = aab aab aaaab$
$suf1 = aab aaaab$
$pre = aab$
 
Observam astfel ca daca sirul $S$ se potriveste cu sufixul sau pe cel putin $k * |pre|$ caractere, atunci $S$ are un prefix de lungime $(k+1) * |pre|$ care este periodic. Folosindu-ne de structura de date $siruri de sufixe$, putem determina pentru fiecare sufix potrivirea maxima cu sirul initial. Daca al $i$-lea sufix se potiveste cu sirul pe primele $k * (i-1)$ pozitii, atunci putem actualiza informatia care indica daca prefixele de dimensiune $j * (i-1)$ (unde $2 &le; j &le; k$) sunt periodice. Pentru fiecare sufix $S$, actualizarea tuturor informatiilor are ordinul de complexitate $O(n / (i-1))$. Astfel, ordinul de complexitate al algoritmului de rezolvare a acestei probleme este $O(n log n)$. Trebuie remarcat faptul ca putem obtine o rezolvare in timp $O(n)$ folosind o idee similara si algoritmul $KMP$, dar prezentarea acestei rezolvari depaseste scopul acestui articol.
 
h2(#concluzii). Concluzii
 
Mentionam ca in timpul concursurilor autorii prefera solutiile ale caror ordine de complexitate sunt $O(n log^2^ n)$, mai lente, dar mai usor de implementat, si care folosesc un spatiu de memorie de ordinul $O(n)$. Din punctul de vedere al timpului real de executie, cele doua tipuri de solutii vor fi comparabile, iar in concurs simplitatea solutiei usureaza foarte mult implementarea si depanarea. Din cele prezentate putem concluziona ca sirurile de sufixe sunt o structura de date usor de implementat si foarte utila. In ultimii ani apar la concursuri tot mai multe probleme care necesita cunoasterea acestora. Mai putem observa si faptul ca polonezii propun probleme destul de grele la olimpiade. Speram ca acest articol va va fi de folos si ca de acum inainte sirurile de sufixe vor fi la indemana oricui are nevoie de ele pentru a le folosi intr-un concurs de informatica.
 
h2(#bibliografie). Bibliografie
 
# 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_':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
# Mohamed Ibrahim Abouelhoda, Stefan Kurtz, Enno Ohlebusch, '_Replacing suffix trees with enhanced suffix arrays_':http://www.zbh.uni-hamburg.de/pubs/pdf/AboKurOhl2004.pdf, Journal of Discrete Algorithms 2, 2004
# Thomas Cormen, Charles Leiserson, Ronald Rivest, '_Introducere in algoritmi_':http://zhuzeyuan.hp.infoseek.co.jp/ita/toc.htm, Editura Computer Libris Agora, 2000
# Dana Lica, '_Arbori de intervale_':arbori-de-intervale
# Cosmin Negruseri, '_Cautari ortogonale_':cautari-ortogonale, GInfo 15/5 (Mai 2005), Editura Agora Media
# 'BOI 2004':http://www.boi2004.lv/

Nu exista diferente intre securitate.

Diferente intre topic forum:

 
3691