Space-Efficient Construction of Compressed Indexes in Deterministic Linear Time

Abstract

We show that the compressed suffix array and the compressed suffix tree of a string $T$ can be built in $O(n)$ deterministic time using $O(n\log \sigma )$ bits of space, where $n$ is the string length and $\sigma$ is the alphabet size. Previously described deterministic algorithms either run in time that depends on the alphabet size or need $\omega (n\log \sigma )$ bits of working space. Our result has immediate applications to other problems, such as yielding the first linear-time LZ77 and LZ78 parsing algorithms that use $O(n\log \sigma )$ bits.

Extended version of a paper to appear at SODA 2017