Lempel-Ziv Computation In Compressed Space (LZ-CICS)

Dominik Köppl, Kunihiko Sadakane

We show that both the Lempel Ziv 77- and the 78-factorization of a text of length $n$ on an integer alphabet of size $\sigma$ can be computed in $O(n\lg \lg \sigma )$ time (linear time if we…