Boyer-Moore string matching over Ziv-Lempel compressed text

Abstract. We present a solution to the problem of performing approx-imate pattern matching on compressed text. The format we choose is the Ziv-Lempel family, specically the LZ78 and LZW variants. Given a text of length u compressed into length n, and a pattern of length m, we report all the R occurrences of the pattern in the text allowing up to k insertions, deletions and substitutions, in O(mkn+R) time. The exis-tence problem needs O(mkn) time. We also show that the algorithm can be adapted to run in O(k 2 n + min(mkn;