Space-Efficient Construction of Compressed Indexes in Deterministic Linear Time

J. Ian Munro, Gonzalo Navarro and 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 s) bits of space, where n is the string length and s is the alphabet size. Previously described deterministic algorithms either run in time that depends on the alphabet size or need omega(n log s) 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 s) bits.