###
Fast Fully-Compressed Suffix Trees

####
Gonzalo Navarro and Luís Russo

We speed up the fully-compressed suffix tree representation (FCST),
which is the only one using asymptotically optimal space. Classical
representations of suffix trees are fast, but require too much space
(*O(n log n)* bits for a string of length *n* over an alphabet of size
*s*, which is considerably more than the *n log s* bits needed
to represent the string). Modern compressed suffix tree representations
are smaller, getting close to the *compressed* string size, and achieve
constant to sublogarithmic time for most operations. However, their space
is not fully optimal. An exception is the FCST, which achieves fully optimal
space but its times are superlogarithmic. Our contribution
significantly accelerates the FCST representation, achieving for many
operations log-logarithmic times on typical texts. The resulting FCST
variant becomes very attractive in terms of space and time, and a promising
alternative in practice.