Solving Classical String Problems on Compressed Texts
<|reference_start|>Solving Classical String Problems on Compressed Texts: 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.<|reference_end|>
@article{lifshits2006solving,
    title={Solving Classical String Problems on Compressed Texts},
    author={Yury Lifshits},
    journal={arXiv preprint arXiv:cs/0604058},
    year={2006},
    archivePrefix={arXiv},
    eprint={cs/0604058},
    primaryClass={cs.DS cs.CC}
}