Pentru a avea o idee mai buna despre _suffix arrays_, vom face înainte o scurta prezentare a structurii de date numita în 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 în general un numar de fii egal cu marimea alfabetului sirurilor de caractere care trebuies stocate. În 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 pâna la o frunza vor alcatui un cuvânt stocat in arbore. Dupa cum se observa, cautarea existentei unui cuvânt în aceasta structura de date este foarte eficienta si se realizeaza în complexitate O(M), unde M e lungimea cuvântului. Astfel, timpul de cautare nu depinde de numarul de cuvinte pe care trebuie sa îl 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 începe la pozitia $i$. Fie $n$ = lungimea lui $A$. Trie-ul de sufixe este format prin comprimarea tuturor sufixelor $A{~1~}...A{~n–1~}$ într-un trie, ca în figura de mai jos.

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 începe la pozitia $i$. Fie $n$ = lungimea lui $A$. Trie-ul de sufixe este format prin comprimarea tuturor sufixelor $A{~1~}…A{~n–1~}$ într-un trie, ca în figura de mai jos.

Trie-ul de sufixe corespunzator stringului $abac$ este:
Operatiile pe aceasta structura se realizeaza extrem de usor:
* verificarea daca un string $W$ este substring al lui $A$ – este suficienta parcurgerea nodurilor, începând 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 sfârsitului celor doua prefixe, iar prin aplicarea unui algoritm de gasire a LCA (least common ancestor / cel mai apropiat stramos comun) se gaseste nodul corespunzator sfârsitului 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 în $O(sqrt(n))$, [3] pentru o prezentare accesibila a unei rezolvari în $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 sfârsitului celor doua prefixe, iar prin aplicarea unui algoritm de gasire a LCA (least common ancestor / cel mai apropiat stramos comun) se gaseste nodul corespunzator sfârsitului 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 în $O(sqrt(n))$, [3] pentru o prezentare accesibila a unei rezolvari în $O(log n)$ sau $O(1)$, si articolul [4] pentru un algoritm _“state of the art”_.

* gasirea celui de-al $k$-lea sufix în ordine lexicografica - (complexitate $O(n)$, cu o preprocesare corespunzatoare). De exemplu al $3$-lea sufix al sirului $abac$ este reprezentat în trie-ul nostru de a $3$-a frunza.