Computing LZ77 in Run-Compressed Space

Nicola Prezza, Alberto Policriti

In this paper, we show that the LZ77 factorization of a text T {\inΣ^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 B…