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 AsGet 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
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.
Keywords
- Pattern matching
- Compressed text
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads