For both the Lempel Ziv 77- and 78-factorization we propose algorithms generating the respective factorization using @math bits (for any positive constant @math ) working space (including the space for the output) for any text of size @math over an integer alphabet in @math time.
LZ78, by using a naive trie implementation, the factorization is computable with @math bits space and @math overall running time, where @math is the size of LZ78 factorization. More sophisticated trie implementations @cite_8 improve this to @math time using the same space.
@cite_8
1884472997
We consider finding a pattern of length (m ) in a compacted (linear-size) trie storing strings over an alphabet of size ( ). In static tries, we achieve (O(m+ ) ) deterministic time, whereas in dynamic tries we achieve (O(m+ ^ 2 ) ) deterministic time per query or update. One particular application of the above bounds (static and dynamic) are suffix trees, where we also show how to pre- or append letters in (O( n + ^ 2 ) ) time. Our main technical contribution is a weighted variant of exponential search trees, which might be of independent interest.