Faster subsequence recognition in compressed strings

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 $\overline m$, and an uncompressed pattern of length $n$, Cégielski et al. gave an algorithm for local subsequence recognition running in time $O(\overline mn^2\log n)$. We improve the running time to $O(\overline 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(\overline mn^{1.5})$; the same problem with a compressed pattern is known to be NP-hard. Bibl. – 22 titles.