Solving Classical String Problems on Compressed Texts
| dc.creator | Lifshits, Yury | |
| dc.date | 2006-04-13 | |
| dc.date.accessioned | 2026-07-07T07:09:22Z | |
| dc.date.available | 2026-07-07T07:09:22Z | |
| dc.description | 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. | |
| dc.description | 10 pages, 6 figures, submitted | |
| dc.identifier | https://arxiv.org/abs/cs/0604058 | |
| dc.identifier | http://arxiv.org/abs/cs/0604058 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/111039 | |
| dc.subject | Data Structures and Algorithms | |
| dc.subject | Computational Complexity | |
| dc.subject | E.4; F.2.2; I.7 | |
| dc.title | Solving Classical String Problems on Compressed Texts | |
| dc.type | text |