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��)$ bits of space, where $n$ is the string length and $��$ is the alphabet size. Previously described deterministic algorithms either run in time that depends on the alphabet size or need $��(n\log ��)$ 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��)$ bits.

Extended version of a paper to appear at SODA 2017