@CONFERENCE\{IMM2007-04831,
    author       = "P. Bille and R. Fagerberg and I. L. G{\o}rtz",
    title        = "Improved Approximate String Matching and Regular Expression Matching on Ziv-Lempel Compressed Texts",
    year         = "2007",
    month        = "jul",
    pages        = "52-62",
    booktitle    = "Proc. 18th Annual Symposium on Combinatorial Pattern Matching ({CPM} 2007)",
    volume       = "4580",
    series       = "Lecture Notes in Computer Science",
    editor       = "",
    publisher    = "Springer",
    organization = "",
    address      = "",
    url          = "http://www2.compute.dtu.dk/pubdb/pubs/4831-full.html",
    abstract     = "In this paper we study the approximate string matching and regular expression matching problem for the case when the text to be searched is compressed with the Ziv-Lempel adaptive dictionary compression schemes. We present a time-space trade-off that leads to algorithms improving the previously known complexities for both problems. In particular, we significantly improve the space bounds. In practical applications the space is likely to be a bottleneck and therefore this is of crucial importance."
}