Show simple item record

dc.contributor.authorCrochemore, M.
dc.contributor.authorIliopoulos, Costas
dc.contributor.authorPissis, S.
dc.contributor.authorTischler, G.
dc.contributor.editorAmihood Amir and Laxmi Parida
dc.identifier.citationCrochemore, 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.

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.

dc.titleCover array string reconstruction
dc.typeConference Paper
dcterms.source.titleLecture notes in computer science, volume 6129: combinatorial pattern matching
dcterms.source.seriesLecture notes in computer science, volume 6129: combinatorial pattern matching
dcterms.source.conference21st Annual Symposium on Combinatorial Pattern Matching, CPM 2010
dcterms.source.conference-start-dateJun 23 2010
dcterms.source.conferencelocationNew York
curtin.departmentDigital Ecosystems and Business Intelligence Institute (DEBII)
curtin.accessStatusFulltext not available

Files in this item


This item appears in the following Collection(s)

Show simple item record