Linear time construction of compressed text indices in compact space
Djamal Belazzougui · 2014
We show that the compressed suffix array and the compressed suffix tree for a string of length n over an integer alphabet of size σ ≤ n can both be built in O(n) (randomized) time using only O(n log σ) bits of working space. The previously fastest construction algorithms that used O(n log σ) bits of space took times O(n log log σ) and O(n logε n) respectively (where ε is any positive constant smaller than 1).