10.4230/LIPICS.STACS.2012.624
Gawrychowski, Pawel
Pawel
Gawrychowski
Tying up the loose ends in fully LZW-compressed pattern matching
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
2012
Article
pattern matching
compression
Lempel-Ziv-Welch
Dürr, Christoph
Christoph
Dürr
Wilke, Thomas
Thomas
Wilke
2012
2012-02-24
2012-02-24
2012-02-24
en
urn:nbn:de:0030-drops-33975
10.4230/LIPIcs.STACS.2012
978-3-939897-35-4
1868-8969
10.4230/LIPIcs.STACS.2012
LIPIcs, Volume 14, STACS 2012
29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)
2013
14
56
624
635
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Dürr, Christoph
Christoph
Dürr
Wilke, Thomas
Thomas
Wilke
1868-8969
Leibniz International Proceedings in Informatics (LIPIcs)
2012
14
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
12 pages
581984 bytes
application/pdf
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
info:eu-repo/semantics/openAccess
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.
LIPIcs, Vol. 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012), pages 624-635