A Simple Algorithm for Computing the Lempel Ziv Factorization
Maxime Crochemore, Lucian Ionel Ilie, W. F. Smyth · DCC · 2008
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 O(n) time independently of alphabet size and uses o(n) additional space.