In computer science, a suffix array is a sorted array of all suffixes of a string. It is a data structure used in, among others, full-text indices, data-compression algorithms, and the field of bibliometrics.

Suffix arrays were introduced by Manber & Myers (1990) as a simple, space efficient alternative to suffix trees. They had independently been discovered by Gaston Gonnet in 1987 under the name PAT array (Gonnet, Baeza-Yates & Snider 1992).

Li, Li & Huo (2016) gave the first in-place ${\displaystyle {\mathcal {O}}(n)}$ time suffix array construction algorithm that is optimal both in time and space, where in-place means that the algorithm only needs ${\displaystyle {\mathcal {O}}(1)}$ additional space beyond the input string and the output suffix array.

Enhanced suffix arrays (ESAs) are suffix arrays with additional tables that reproduce the full functionality of suffix trees preserving the same time and memory complexity. A sorted array of only some (rather than all) suffixes of a string is called a sparse suffix array.

Let ${\displaystyle S=S[1]S[2]...S[n]}$ be an ${\textstyle n}$-string and let ${\displaystyle S[i,j]}$ denote the substring of ${\displaystyle S}$ ranging from ${\displaystyle i}$ to ${\displaystyle j}$ inclusive.

The suffix array ${\displaystyle A}$ of ${\displaystyle S}$ is now defined to be an array of integers providing the starting positions of suffixes of ${\displaystyle S}$ in lexicographical order. This means, an entry ${\displaystyle A[i]}$ contains the starting position of the ${\displaystyle i}$-th smallest suffix in ${\displaystyle S}$ and thus for all ${\displaystyle 1\leq i\leq n}$: ${\displaystyle S[A[i-1],n]<S[A[i],n]}$.

Each suffix of ${\displaystyle S}$ shows up in ${\displaystyle A}$ exactly once. Suffixes are simple strings. These strings are sorted (as in a paper dictionary), before their starting positions (integer indices) are saved in ${\displaystyle A}$.

Consider the text ${\displaystyle S}$=banana$ to be indexed: