Remarks

• The linear time algorithm gsaca-k is at the core of gsufsort. In particular, it is used to compute SA, LCP and DA.

• For inputs larger than 2GB, gsufsort-64 uses 21N bytes to compute SA, LCP and DA (GESA).

working memory (in bytes)

version	32 bits	64 bits
SA	5N	9N
SA+LCP	9N	17N
SA+LCP+DA	13N	21N
SA+DA	9N	13N
GSA	9N	13N
GESA	13N	21N

lightweight version

• There is a lightweight version of gsufsort (option --light) to compute DA using a bitvector during the output to disk, which saves 4N bytes.

• For inputs larger than 2GB, the lightweight version uses 17N bytes to compute SA, LCP and DA (GESA).