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.date.accessioned2017-01-30T10:41:13Z
dc.date.available2017-01-30T10:41:13Z
dc.date.created2015-03-03T20:13:40Z
dc.date.issued2010
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.
dc.identifier.urihttp://hdl.handle.net/20.500.11937/4731
dc.identifier.doi10.1007/978-3-642-13509-5_23
dc.description.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.

dc.publisherSpringer
dc.relation.urihttp://www.springerlink.com/content/dp018wx682v562w1
dc.titleCover array string reconstruction
dc.typeConference Paper
dcterms.source.volume101
dcterms.source.number3
dcterms.source.startPage251
dcterms.source.endPage259
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.isbn9783642135088
dcterms.source.conference21st Annual Symposium on Combinatorial Pattern Matching, CPM 2010
dcterms.source.conference-start-dateJun 23 2010
dcterms.source.conferencelocationNew York
dcterms.source.placeHeidelberg
curtin.departmentDigital Ecosystems and Business Intelligence Institute (DEBII)
curtin.accessStatusFulltext not available


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record