Suffix array

Suffix array
Type	Array
Invented by	Manber & Myers (1990)
	Average	Worst case
Space	${\displaystyle {\mathcal {O}}(n)}$	${\displaystyle {\mathcal {O}}(n)}$
Construction	${\displaystyle {\mathcal {O}}(n)}$	${\displaystyle {\mathcal {O}}(n)}$

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

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

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

...
Wikipedia