Cover array string reconstruction
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[...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Conference Paper |
| Published: |
Springer
2010
|
| Online Access: | http://www.springerlink.com/content/dp018wx682v562w1 http://hdl.handle.net/20.500.11937/4731 |
| _version_ | 1848744598192521216 |
|---|---|
| author | Crochemore, M. Iliopoulos, Costas Pissis, S. Tischler, G. |
| author2 | Amihood Amir |
| author_facet | Amihood Amir Crochemore, M. Iliopoulos, Costas Pissis, S. Tischler, G. |
| author_sort | Crochemore, M. |
| building | Curtin Institutional Repository |
| collection | Online Access |
| description | 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. |
| first_indexed | 2025-11-14T06:04:00Z |
| format | Conference Paper |
| id | curtin-20.500.11937-4731 |
| institution | Curtin University Malaysia |
| institution_category | Local University |
| last_indexed | 2025-11-14T06:04:00Z |
| publishDate | 2010 |
| publisher | Springer |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | curtin-20.500.11937-47312022-12-09T07:12:35Z Cover array string reconstruction Crochemore, M. Iliopoulos, Costas Pissis, S. Tischler, G. Amihood Amir Laxmi Parida 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. 2010 Conference Paper http://hdl.handle.net/20.500.11937/4731 10.1007/978-3-642-13509-5_23 http://www.springerlink.com/content/dp018wx682v562w1 Springer restricted |
| spellingShingle | Crochemore, M. Iliopoulos, Costas Pissis, S. Tischler, G. Cover array string reconstruction |
| title | Cover array string reconstruction |
| title_full | Cover array string reconstruction |
| title_fullStr | Cover array string reconstruction |
| title_full_unstemmed | Cover array string reconstruction |
| title_short | Cover array string reconstruction |
| title_sort | cover array string reconstruction |
| url | http://www.springerlink.com/content/dp018wx682v562w1 http://hdl.handle.net/20.500.11937/4731 |