Almost optimal fully compressed pattern matching

A {\sl string matching} problem is to find all occurrences of pattern $\P$ in text $\T$.
Assume that both strings $\P$ and $\T$ are given in compressed forms
$p$ and $t$ respectively, where $|p|=m$ and $|t|=n$.
A {\sl fully compressed string matching} problem is to find all occurrences
of $\P$ in $\T$ when only compressed forms of input strings are available.
We present first, almost optimal, fully compressed string matching algorithms
for LZW-compressed strings running in:
\begin{quote}
1. $O((n+m)\log(n+m))$-time on a single processor machine, and with\\
2. $\O(n+m)$ work on a ($n+m$)-processor PRAM\footnote{Notation $\O(g(k))$ stands
for $O(g(k)\log^c(k))$,
for some constant $c\in {\cal R^+}$}.
\end{quote}
Presented techniques 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 an LZW-compressed text, finding repetitions, symmetries, counting
subwords, and multi-pattern matching.