Cover array string reconstruction

Crochemore, M.; Iliopoulos, Costas; Pissis, S.; Tischler, G.

doi:10.1007/978-3-642-13509-5_23

Access Status

Fulltext not available

Authors

Crochemore, M.

Iliopoulos, Costas

Pissis, S.

Tischler, G.

Date

2010

Type

Conference Paper

Metadata

Show full item record

Citation

Crochemore, M. and Iliopoulos, C. and Pissis, S. and Tischler, G. 2010. Cover array string reconstruction, in Amihood Amir and Laxmi Parida (ed), 21st Annual Symposium on Combinatorial Pattern Matching, CPM 2010, Jun 23 2010, pp. 251-259. New York: Springer.

Source Title

Lecture notes in computer science, volume 6129: combinatorial pattern matching

Source Conference

21st Annual Symposium on Combinatorial Pattern Matching, CPM 2010

School

Digital Ecosystems and Business Intelligence Institute (DEBII)

URI

http://hdl.handle.net/20.500.11937/4731

Collection

Curtin Research Publications

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 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 coverarrays: the sum of important values in a cover array is bounded by twice the length of the string.