###
Indexing Text using the Ziv-Lempel Trie

####
Gonzalo Navarro

Let a text of *u* characters over an alphabet of size *s* be
compressible to *n* symbols by the LZ78 or LZW algorithm. We show that it
is possible to build a data structure based on the Ziv-Lempel trie that takes
*4n log_2 n (1+o(1))* bits of space and reports the *R* occurrences
of a pattern of length *m* in worst case time *O(m^2 log (ms) + (m+R)
log n)*.