Approximate pattern matching in LZ77-compressed texts

Suppose we want to support approximate pattern matching in a text T[1..n]T[1..n] whose LZ77 parse consists of z phrases. In this paper we show how, given that parse, we can preprocess T   in O(zlog⁡n)O(zlog⁡n) time and space such that later, given a pattern P[1..m]P[1..m] and an edit distance k  , we can perform approximate pattern matching in O(zmin⁡(mk,m+k4)+occ)O(zmin⁡(mk,m+k4)+occ) time and O(zlog⁡n+m+occ)O(zlog⁡n+m+occ) space, where occ is the size of the output.