Arranjo de sufixos
Em ciência da computação, um array de sufixos é um array ordenado de todos os sufixos de uma cadeia de caracteres. É uma estrutura de dados simples, porém poderosa que é usada, dentre outras, em índices de textos inteiros, algoritmos de compressão de dados e dentro do campo da bioinformática.
Seja S = s 1 , s 2 , . . . , s n {\displaystyle S=s_{1},s_{2},...,s_{n}} uma cadeia de caracteres e seja S [ i , j ] {\displaystyle S[i,j]} a subcadeia de S {\displaystyle S} que vai de i {\displaystyle i} até j {\displaystyle j} . O array de sufixos A {\displaystyle A} de S {\displaystyle S} é definido como sendo um array de inteiros que proveem as posições iniciais dos sufixos de S {\displaystyle S} em ordem lexicográfica. Isto significa que uma entrada A [ i ] {\displaystyle A[i]} contem a posição inicial do i {\displaystyle i} -ésimo menor sufixo em S {\displaystyle S} e, da mesma forma, para todo 1 < i ≤ n {\displaystyle 1<i\leq n} : S [ A [ i − 1 ] , n ] < S [ A [ i ] , n ] {\displaystyle S[A[i-1],n]<S[A[i],n]} .
Considere o texto S=banana$ a ser indexado: O texto termina com a letra sentinela especial $, que é único e lexicograficamente menor do que qualquer outro caractere. O texto possui os seguintes sufixos: O array de sufixos A contém a posição inicial destes sufixos ordenados: Então por exemplo, A contém o valor 4, e por isso, se refere ao sufixo iniciando na posição 4 dentro de S, que é o sufixo ana$.
