Space Efficient Linear Time Lempel-Ziv Factorization on Constant~Size~Alphabets

Keisuke Goto, Hideo Bannai

We present a new algorithm for computing the Lempel-Ziv Factorization (LZ77) of a given string of length $N$ in linear time, that utilizes only $N\log N+O(1)$ bits of working spa…