Computer Science – Data Structures and Algorithms
Scientific paper
2011-04-21
Computer Science
Data Structures and Algorithms
submitted
Scientific paper
Countless variants of the Lempel-Ziv compression are widely used in many real-life applications. This paper is concerned with a natural modification of the classical pattern matching problem inspired by the popularity of such compression methods: given an uncompressed pattern s[1..m] and a Lempel-Ziv representation of a string t[1..N], does s occur in t? Farach and Thorup gave a randomized O(nlog^2(N/n)+m) time solution for this problem, where n is the size of the compressed representation of t. We improve their result by developing a faster and fully deterministic O(nlog(N/n)+m) time algorithm with the same space complexity. Note that for highly compressible texts, log(N/n) might be of order n, so for such inputs the improvement is very significant. A (tiny) fragment of our method can be used to give an asymptotically optimal solution for the substring hashing problem considered by Farach and Muthukrishnan.
No associations
LandOfFree
Pattern matching in Lempel-Ziv compressed strings: fast, simple, and deterministic does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Pattern matching in Lempel-Ziv compressed strings: fast, simple, and deterministic, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Pattern matching in Lempel-Ziv compressed strings: fast, simple, and deterministic will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-178003