Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4952351 | Theoretical Computer Science | 2016 | 8 Pages |
Abstract
Assume we are given a sorted set P of size n of all periods of an unknown string of size N. Our main result is an algorithm generating in O(n) time and O(1) space a compressed representation of size O(n) of the lexicographically-first binary string having P as the set of its periods. The input is read-only and the output is write-only. We also present a very simple preliminary algorithm generating some binary string (not necessarily lexicographically-first one) with the same set of periods. The explicit size N of the produced string can be exponential with respect to n. We assume that a given set of periods is valid: there exists some unknown string realizing this set.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Wojciech Rytter,