LZ77

In this paper, we show that the LZ77 factorization of a text T ∈ Σn can be computed in O(R log n) bits of working space and O(n log R) time, R being the number of runs in the Burrows-Wheeler transform of T (reversed). For (extremely) repetitive …