Esta estructura de datos es muy simple, sin embargo es muy poderosa y es usada en algoritmos de compresión de datos y dentro del campo de la bioinformática , indización de textos completos, entre otros.

Los arreglos de sufijos fueron introducidos por Manber y Myers (1990) como una simple variante eficiente en espacio a los árboles de sufijos.

Estos fueron descubiertos independientemente por Gonnet, Baeza-Yates y Snider (1992) bajo el nombre de arreglo PAT.

contiene la posición inicial del

y por tanto se cumple que para todo

{\displaystyle S[A[i-1],n]

a ser indexado: El texto termina con el carácter especial $ el cual debe ser único dentro de la cadena y lexicográficamente más pequeño que cualquier otro carácter.El texto contiene los siguientes sufijos: Estos sufijos pueden ser ordenados : El arreglo de sufijos

conteniendo las posiciones iniciales de los sufijos ordenados : Por ejemplo,

y por tanto se refiere al sufijo que empieza el la posición

Los arreglos de sufijos están muy relacionados con los árboles de sufijos: Ha sido demostrado todo algoritmo de árbol de sufijos puede ser sistemáticamente reemplazado con un algoritmo que use un arreglo de sufijos unido con información adicional (como un arreglo de prefijos comunes) y resuelve el mismo problema y con la misma complejidad temporal.

Los arreglos de sufijos fueron introducidos por Manber y Myers (1990) para obtener una mejora en cuanto a los requerimientos en espacio de los árboles de sufijos : los arreglos de sufijos guardan

bytes, un arreglo de sufijos requiere un total de implementación

Esto es significantemente mucho menor que los

bytes requeridos en implementación cuidadosa de un árbol de sufijos.

[2]​ Sin embargo, en ciertas aplicaciones, los requerimientos en espacio de los arreglos de sufijos pueden ser prohibitivos.Analizando en cuanto a bits, un arreglo de sufijos requiere un espacio de

, donde el texto original sobre un alfabeto de longitud

Una primera idea para construir un arreglo de sufijos es usar un método de ordenamiento basado en comparación.

Algoritmos más avanzados toman ventaja del hecho de que los sufijos a ordenar no son cadenas arbitrarias sino que está relacionadas unas con otras.Estos algoritmos tratan de priorizar los siguientes objetivos: Uno de los primeros algoritmos en cumplir todos los objetivos es el algoritmo SA-IS de Nong, Zhang y Chan (2009).

El algoritmo es también muy simple (< 100 LOC y puede ser mejorado para simultáneamente construir el arreglo de prefijos comunes.

Una cuidadosa implementanción implementation by Yuta Mori Archivado el 26 de julio de 2014 en Wayback Machine.

que supera a la mayoría de otros métodos de construcción lineales o super lineales.

El arreglo de sufijos de una cadena puede ser usado como un índice para hallar rápidamente todas las ocurrencias de una subcadena

.Hallar todas la ocurrencias de un patrón es equivalente a hallar todo sufijo que empiece con la subcadena.

Gracias al ordenamiento lexicográfico, los sufijos pueden ser agrupados juntos en el arreglo de sufijos y pueden ser hallados eficientementes con dos búsquedas binarias.

La primera búsqueda localiza la posición inicial del intervalo, y la segunda determina la posición final: Hallar el patrón

, dado que solo se necesita una simple comparación de sufijos para comparar

caracteres.Manber y Myers (1990) describe como esta cota se puede mejorar a

usando un arreglo de prefijos comunes.Abouelhoda, Kurtz y Ohlebusch (2004) mejoró la cota e incluso obtuvo un tiempo de búsqueda de

como el del árbol de sufijos.