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, and an uncompressed pattern of length n, Cégielski et al. gave an algorithm for local subsequence recognition running in time O(mn2) . We improve the running time to O(mn1.5) . Our algorithm can also be used to compute the longest common subsequence between a compressed text and an uncompressed pattern in time O(m n1.5); the same problem with a compressed pattern is known to be NP-hard. Bibliography: 22 titles. © 2009 Springer Science+Business Media, Inc.