Almost optimal fully LZW-compressed pattern matching

Leszek Gasieniec, Wojciech Rytter

Research output: Chapter in Book/Report/Conference proceedingConference contribution

26 Scopus citations


Given two strings: pattern P and text T of lengths |P| = M and |T| = N. A string matching problem is to find all occurrences of pattern P in text T. A fully compressed string matching problem is the string matching problem with input strings P and T given in compressed forms p and t respectively, where |p| = m and |t| = n. We present first, almost optimal, string matching algorithms for LZW-compressed strings running in: 1. O((n + m) log (n + m))-time on a single processor machine, and 2. qq(n + m) work on a (n + m)-processor PRAM. Techniques used in our paper can be used in design of efficient algorithms for a wide range of the most typical string problems, in the compressed LZW setting, including: computing a period of a word, finding repetitions, symmetries, counting subwords, and multi-pattern matching.

Original languageEnglish (US)
Title of host publicationData Compression Conference Proceedings
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages10
ISBN (Print)076950096X
StatePublished - Jan 1 1999
Externally publishedYes
EventProceedings of the 1999 Data Compression Conference, DCC-99 - Snowbird, UT, USA
Duration: Mar 29 1999Mar 31 1999

Publication series

NameData Compression Conference Proceedings
ISSN (Print)1068-0314


ConferenceProceedings of the 1999 Data Compression Conference, DCC-99
CitySnowbird, UT, USA

ASJC Scopus subject areas

  • Computer Networks and Communications


Dive into the research topics of 'Almost optimal fully LZW-compressed pattern matching'. Together they form a unique fingerprint.

Cite this