(Categoria _Algoritmi_, Autori _Adrian Vladu, Negruseri Cosmin_)

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

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. Ce sunt sirurile de sufixe (suffix arrays)?

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.

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?

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.

#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], [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)$.

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.

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.