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.