License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.06201.7
URN: urn:nbn:de:0030-drops-7984
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2006/798/
|
Go to the corresponding Portal |
Lifshits, Yury
Solving Classical String Problems an Compressed Texts
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.
BibTeX - Entry
@InProceedings{lifshits:DagSemProc.06201.7,
author = {Lifshits, Yury},
title = {{Solving Classical String Problems an Compressed Texts}},
booktitle = {Combinatorial and Algorithmic Foundations of Pattern and Association Discovery},
pages = {1--10},
series = {Dagstuhl Seminar Proceedings (DagSemProc)},
ISSN = {1862-4405},
year = {2006},
volume = {6201},
editor = {Rudolf Ahlswede and Alberto Apostolico and Vladimir I. Levenshtein},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2006/798},
URN = {urn:nbn:de:0030-drops-7984},
doi = {10.4230/DagSemProc.06201.7},
annote = {Keywords: Pattern matching, Compressed text}
}
|
Keywords: |
|
Pattern matching, Compressed text |
|
Collection: |
|
06201 - Combinatorial and Algorithmic Foundations of Pattern and Association Discovery |
|
Issue Date: |
|
2006 |
|
Date of publication: |
|
10.11.2006 |
