A simple algorithm for computing the Lempel-Ziv factorization

We give a space-efficient simple algorithm for computing the Lempel—Ziv factorization of a string. For a string of length $n$ over an integer alphabet, it runs in ${\cal O}(n)$ time independently of alphabet size and uses $o(n)$ additional space.