A fully compressed pattern matching algorithm for simple collage systems

We consider a fully compressed pattern matching prob-lem, where both text T and pattern P are given by its suc-cinct representation, in terms of straight-line programs and its variant. The length of the text T and pattern P may grow exponentially with respect to its description size n and m, respectively. The best known algorithm for the problem runs in O(n2m2) time using O(nm) space. In this paper, we introduce a variant of straight-line programs, called bal-anced straight-line programs so that we establish a faster fully compressed pattern matching algorithm. Although the compression ratio of balanced straight-line programs may be worse than the original straight-line programs, they can still express exponentially long strings. Our algorithm runs in O(nm) time using O(nm) space.