Cover array string reconstruction
Access Status
Authors
Date
2010Type
Metadata
Show full item recordCitation
Source Title
Source Conference
Additional URLs
ISBN
School
Collection
Abstract
A proper fact or u of a string y is a cover of y if every letter of y is within some occurrence of u in y. The concept generalises the notion of periods of a string. An integer array C is the minimalcover (resp. maximalcover) array of y if C[i] is the minimal (resp. maximal) length of covers of y[0 ..i], or zero if no cover exists. In this paper, we present a constructive algorithm checking the validity of an array as a minimalcover or maximalcover array of some string. When the array is valid, the algorithm produces a string over an unbounded alphabet whose cover array is the input array. All algorithms run in linear time due to an interesting combinatorial property of coverarrays: the sum of important values in a cover array is bounded by twice the length of the string.
Related items
Showing items related by title, author, creator and subject.

Iliopoulos, Costas; Mohamed, M.; Smyth, William (2011)The kcovers problem (kCP) asks us to compute a minimum cardinality set of strings of given length k > 1 that covers a given string. It was shown in a recent paper, by reduction to 3SAT, that the kcovers problem is ...

Crochemore, M.; Iliopoulos, Costas; Kubica, M.; Rytter, W.; Walen, T. (2010)Su?x arrays provide a powerful data structure to solve several questions related to the structure of all the factors of a string. We show how they can be used to compute e?ciently two new tables storing di?erent types of ...

Puglisi, Simon; Smyth, William; Yusufu, M. (2010)Given a string x = x[1..n] on an alphabet of size α, and a threshold p min ≥ 1, we describe four variants of an algorithm PSY1 that, using a suffix array, computes all the complete nonextendible repeats in x of length p ...