Editing Suffix array (section)

{{Short description|Data structure for a string}}
{{Infobox
| above =  Suffix array
| label1 = [[List of data structures|Type]]
| data1 = [[Array data structure|Array]]
| label2 = Invented by
| data2 = {{harvtxt|Manber|Myers|1990}}
| header3 = [[Time complexity]]<br />in [[big O notation]]
| headerstyle = background:lavender
| data4 = 
{{aligned table|cols=3|row1header=y|col1header=y|fullwidth=y
| | Average | Worst case
<!-- -->
| Space
| <math>\mathcal{O}(n)</math>
| <math>\mathcal{O}(n)</math>
<!-- -->
| Construction
| <math>\mathcal{O}(n)</math>
| <math>\mathcal{O}(n)</math>
}}
}}
In [[computer science]], a '''suffix array''' is a sorted [[Array data structure|array]] of all [[Suffix (computer science)|suffixes]] of a [[String (computer science)|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 {{harvtxt|Manber|Myers|1990}} as a simple, space efficient alternative to [[suffix tree]]s. They had independently been discovered by [[Gaston Gonnet]] in 1987 under the name ''PAT array'' {{harv|Gonnet|Baeza-Yates|Snider|1992}}.

{{harvtxt|Li|Li|Huo|2016}} gave the first in-place <math>\mathcal{O}(n)</math> time suffix array construction algorithm that is optimal both in time and space, where ''in-place'' means that the algorithm only needs <math>\mathcal{O}(1)</math> 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.{{sfn|Abouelhoda|Kurtz|Ohlebusch|2004}}
A sorted array of only some (rather than all) suffixes of a string is called a [[sparse suffix array]].{{sfn|I|Kärkkäinen|Kempa|2014}}