Faster subsequence recognition in compressed strings

Abstract

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