  Computation on compressed strings is one of the key approaches to processing
massive data sets. We consider local subsequence recognition problems on
strings compressed by straight-line programs (SLP), which is closely related to
Lempel--Ziv compression. For an SLP-compressed text of length $\bar m$, and an
uncompressed pattern of length $n$, C{\'e}gielski et al. gave an algorithm for
local subsequence recognition running in time $O(\bar mn^2 \log n)$. We improve
the running time to $O(\bar mn^{1.5})$. Our algorithm can also be used to
compute the longest common subsequence between a compressed text and an
uncompressed pattern in time $O(\bar mn^{1.5})$; the same problem with a
compressed pattern is known to be NP-hard.
