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:

| $abac$ | $A{~0~}$ |
| $ac$ | $A{~2~}$ |
| $bac$ | $A{~1~}$ |
| $c$ | $A{~3~}$ |

| *$abac$* | $A{~0~}$ |
| *$ac$* | $A{~2~}$ |
| *$bac$* | $A{~1~}$ |
| *$c$* | $A{~3~}$ |
 
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)?
 
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 $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: