Solving Classical String Problems on Compressed Texts

Details Solving Classical String Problems on Compressed Texts Solving Classical String Problems on Compressed Texts

2006-04-13

arxiv.org/abs/cs/0604058v1

Computer Science

Data Structures and Algorithms

10 pages, 6 figures, submitted

Scientific paper

Here we study the complexity of string problems as a function of the size of a program that generates input. We consider straight-line programs (SLP), since all algorithms on SLP-generated strings could be applied to processing LZ-compressed texts. The main result is a new algorithm for pattern matching when both a text T and a pattern P are presented by SLPs (so-called fully compressed pattern matching problem). We show how to find a first occurrence, count all occurrences, check whether any given position is an occurrence or not in time O(n^2m). Here m,n are the sizes of straight-line programs generating correspondingly P and T. Then we present polynomial algorithms for computing fingerprint table and compressed representation of all covers (for the first time) and for finding periods of a given compressed string (our algorithm is faster than previously known). On the other hand, we show that computing the Hamming distance between two SLP-generated strings is NP- and coNP-hard.

Affiliated with

Also associated with

No associations

Rating

Solving Classical String Problems on Compressed Texts does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Solving Classical String Problems on Compressed Texts, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Solving Classical String Problems on Compressed Texts will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-514632