Two fast constructions of compact representations of binary words with given set of periods

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.