Computing longest common substring and all palindromes from compressed strings

Abstract. This paper studies two problems on compressed strings de-scribed in terms of straight line programs (SLPs). One is to compute the length of the longest common substring of two given SLP-compressed strings, and the other is to compute all palindromes of a given SLP-compressed string. In order to solve these problems efficiently (in poly-nomial time w.r.t. the compressed size) decompression is never feasible, since the decompressed size can be exponentially large. We develop com-binatorial algorithms that solve these problems in O(n4 log n) time with O(n3) space, and in O(n4) time with O(n2) space, respectively, where n is the size of the input SLP-compressed strings.