License: 
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2012.624
URN: urn:nbn:de:0030-drops-33975
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2012/3397/
Gawrychowski, Pawel
Tying up the loose ends in fully LZW-compressed pattern matching
Abstract
We consider a natural generalization of the classical pattern matching problem: given compressed representations of a pattern p[1..M] and a text t[1..N] of sizes m and n, respectively, does p occur in t? We develop an optimal linear time solution for the case when p and t are compressed using the LZW method. This improves the previously known O((n+m)log(n+m)) time solution of Gasieniec and Rytter, and essentially closes the line of research devoted to tudying LZW-compressed exact pattern matching.
BibTeX - Entry
@InProceedings{gawrychowski:LIPIcs:2012:3397,
author = {Pawel Gawrychowski},
title = {{Tying up the loose ends in fully LZW-compressed pattern matching}},
booktitle = {29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
pages = {624--635},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-35-4},
ISSN = {1868-8969},
year = {2012},
volume = {14},
editor = {Christoph D{\"u}rr and Thomas Wilke},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2012/3397},
URN = {urn:nbn:de:0030-drops-33975},
doi = {10.4230/LIPIcs.STACS.2012.624},
annote = {Keywords: pattern matching, compression, Lempel-Ziv-Welch}
}
|
Keywords: |
|
pattern matching, compression, Lempel-Ziv-Welch |
|
Collection: |
|
29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012) |
|
Issue Date: |
|
2012 |
|
Date of publication: |
|
24.02.2012 |
