Skip to Main content Skip to Navigation
Conference papers

Cover array string reconstruction

Abstract : A proper factor 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 minimal-cover (resp. maximal-cover) 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 minimal-cover or maximal-cover 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 cover arrays: the sum of important values in a cover array is bounded by twice the length of the string.
Document type :
Conference papers
Complete list of metadatas

https://hal-upec-upem.archives-ouvertes.fr/hal-00742038
Contributor : Maxime Crochemore <>
Submitted on : Wednesday, February 13, 2013 - 10:19:37 AM
Last modification on : Wednesday, February 26, 2020 - 7:06:06 PM
Long-term archiving on: : Tuesday, May 14, 2013 - 4:00:08 AM

File

Cover_array_string_reconstruct...
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00742038, version 1

Citation

Maxime Crochemore, Costas S. Iliopoulos, Solon P. Pissis, German Tischler. Cover array string reconstruction. CPM, 2010, New-York, United States. pp.251-259. ⟨hal-00742038⟩

Share

Metrics

Record views

299

Files downloads

335