Suffix Array

data-structures string-algorithms

Definition

Suffix Array

A suffix array for a string $T$ is an array of the starting positions of the suffixes of $T$$, sorted in lexicographic order.

If $SA[k]=i$, then the $k$-th sorted suffix starts at position $i$.

Examples

Suffix array of $\text{banana}$

For $T=\text{banana}$, append the fresh letter \$$. The suffixes of T’ = \text{banana}$$ in lexicographic order are:

$$\$,\text{a}\$,\text{ana}\$,\text{anana}\$,\text{banana}\$,\text{na}\$,\text{nana}\$.$$

Their starting positions are:

$$SA=[6,5,3,1,0,4,2].$$

Substring lookup

A pattern $P$ occurs in $T$ at exactly those suffix-array positions whose suffixes have $P$ as a prefix.

For $T=\text{banana}$ and $P=\text{ana}$, the matching suffixes are \text{ana}\$$ and \text{anana}$$.Theirsuffix-arrayentriesare$3$and$1$,so$\text{ana}$occursatpositions$3$and$1$in$T$.