  We present an algorithm that computes the Lempel-Ziv decomposition in
$O(n(\log\sigma + \log\log n))$ time and $n\log\sigma + \epsilon n$ bits of
space, where $\epsilon$ is a constant rational parameter, $n$ is the length of
the input string, and $\sigma$ is the alphabet size. The $n\log\sigma$ bits in
the space bound are for the input string itself which is treated as read-only.
