Cover array string reconstruction
| dc.contributor.author | Crochemore, M. | |
| dc.contributor.author | Iliopoulos, Costas | |
| dc.contributor.author | Pissis, S. | |
| dc.contributor.author | Tischler, G. | |
| dc.contributor.editor | Amihood Amir | |
| dc.contributor.editor | Laxmi Parida | |
| dc.date.accessioned | 2017-01-30T10:41:13Z | |
| dc.date.available | 2017-01-30T10:41:13Z | |
| dc.date.created | 2015-03-03T20:13:40Z | |
| dc.date.issued | 2010 | |
| dc.identifier.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. | |
| dc.identifier.uri | http://hdl.handle.net/20.500.11937/4731 | |
| dc.identifier.doi | 10.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.publisher | Springer | |
| dc.relation.uri | http://www.springerlink.com/content/dp018wx682v562w1 | |
| dc.title | Cover array string reconstruction | |
| dc.type | Conference Paper | |
| dcterms.source.volume | 101 | |
| dcterms.source.number | 3 | |
| dcterms.source.startPage | 251 | |
| dcterms.source.endPage | 259 | |
| dcterms.source.title | Lecture notes in computer science, volume 6129: combinatorial pattern matching | |
| dcterms.source.series | Lecture notes in computer science, volume 6129: combinatorial pattern matching | |
| dcterms.source.isbn | 9783642135088 | |
| dcterms.source.conference | 21st Annual Symposium on Combinatorial Pattern Matching, CPM 2010 | |
| dcterms.source.conference-start-date | Jun 23 2010 | |
| dcterms.source.conferencelocation | New York | |
| dcterms.source.place | Heidelberg | |
| curtin.department | Digital Ecosystems and Business Intelligence Institute (DEBII) | |
| curtin.accessStatus | Fulltext not available |