We give first the representation of a suffix tree that uses nlgn+ O (n) bits of space and
supports searching for a pattern string in the given text (from a fixed size alphabet) in O (m)
time, where n is the size of the text and m is the length of the pattern. The structure is quite
simple and answers a question raised by Muthukrishnan (in Proceedings of the FST and
TCS Preconference Workshop on Randomization, 1997, pp. 23–27). Previous compact
representations of suffix trees had either a higher lower order term in space and had some …