Almost optimal fully LZW-compressed pattern matching

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.