Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
431632 | Journal of Discrete Algorithms | 2015 | 5 Pages |
Abstract
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(zlogn)O(zlogn) 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(zlogn+m+occ)O(zlogn+m+occ) space, where occ is the size of the output.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Travis Gagie, Paweł Gawrychowski, Simon J. Puglisi,