DagSemProc.06201.7.pdf
- Filesize: 224 kB
- 10 pages
Document
Solving Classical String Problems an Compressed Texts
Author
-
Part of:
Volume:
Dagstuhl Seminar Proceedings, Volume 6201
Series: Dagstuhl Seminar Proceedings (DagSemProc) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2006-11-10
Cite As Get BibTex
Yury Lifshits. Solving Classical String Problems an Compressed Texts. In Combinatorial and Algorithmic Foundations of Pattern and Association Discovery. Dagstuhl Seminar Proceedings, Volume 6201, pp. 1-10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)
https://doi.org/10.4230/DagSemProc.06201.7
Abstract
How to solve string problems, if instead of input string we get only program generating it? Is it possible to solve problems faster than just "generate text + apply classical algorithm"? In this paper we consider strings generated by straight-line programs (SLP). These are programs using only assignment operator. We show new algorithms for equivalence, pattern matching, finding periods and covers, computing fingerprint table on SLP-generated strings. From the other hand, computing the Hamming distance is NP-hard. Main corollary is an $O(n2*m)$ algorithm for pattern matching in LZ-compressed texts.
Subject Classification
Keywords
- Pattern matching
- Compressed text
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads