Space-Efficient Construction of Compressed Indexes in Deterministic Linear Time

J. Ian Munro, Gonzalo Navarro, Yakov Nekrich

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…