Algoritmul se bazeaza pe mentinerea ordinii sufixelor sirului, sortate dupa prefixele lor de lungime $2k$. Astfel vom executa $m$ = $[log{~2~}n]$ (marginit superior) pasi, la pasul $k$ stabilind ordinea sufixelor daca sunt luate in considerare doar primele $2k$ caractere din fiecare sufix. Se foloseste o matrice $P$ de dimensiune $m x n$. Notam cu $A{~i~}^k^$ subsecventa lui $A$ de lungime $2k$ 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)~}$.
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 $2k+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+2k$ 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 $2k+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:
Iata un pseudocod ce sugereaza pasii principali ce trebuie urmati:
== code(c) |
n <- lungime(A)
pentru i <- 0, n – 1
P(0, i) <- pozitia in sirul ordonat al caracterelor lui A a lui Ai
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)
sorteaza L
calculeaza P(k, i), i = 0,n-1
cnt <- 2 * cnt
==
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$.
Mai jos puteti vedea o implementare extrem de scurta pentru suffix array in $O(n lg^2^ n)$.
== code(cpp) |
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAXN 65536
#define MAXLG 17
char A[MAXN];
struct entry {
int nr[2], p;
} 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);
}
int main(void)
{
gets(A);
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 ++)
{
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 ++)
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.