Suffix array

In <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, a suffix array is a sorted <a href="/facts/Array_data_structure/BKGvF8AM">array</a> of all <a href="/facts/Suffix_(computer_science)/dM5Rqg6X">suffixes</a> of a <a href="/facts/String_(computer_science)/4ChJu5WS">string</a>. It is a data structure used in, among others, full-text indices, data-compression algorithms, and the field of <a href="/facts/Bibliometrics/PaWjjRuW">bibliometrics</a>.
Suffix arrays were introduced by Manber & Myers (1990) as a simple, space efficient alternative to <a href="/facts/Suffix_tree/pdQdCxbe">suffix trees</a>. They had independently been discovered by <a href="/facts/Gaston_Gonnet/L2HhgeVo">Gaston Gonnet</a> in 1987 under the name PAT array (Gonnet, Baeza-Yates & Snider 1992).
Li, Li & Huo (2016) gave the first in-place 
 
 
 
 
 
 O
 
 
 (
 n
 )
 
 
 {\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 
 
 
 
 
 
 O
 
 
 (
 1
 )
 
 
 {\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.

Suffix array open-in-new

Suffix array