On the maximal number of cubic runs in a string
A run is an inclusion maximal occurrence in a string (as a subinterval) of a repetition v with a period p such that 2p =|v|.The maximal number of runs in a string of length n has been thoroughly studied, and is known to be between 0.944 n and 1.029 n.In this paper we investigate cubic runs, in which...
| Main Authors: | , , , , , |
|---|---|
| Other Authors: | |
| Format: | Conference Paper |
| Published: |
Springer
2010
|
| Online Access: | http://www.springerlink.com/content/73w55281j86r8w18 http://hdl.handle.net/20.500.11937/45763 |
| _version_ | 1848757375606980608 |
|---|---|
| author | Crochemore, M. Iliopoulos, Costas Kubica, M. Radoszewski, J. Rytter, W. Walen, T. |
| author2 | Adrian-Horia Dediu |
| author_facet | Adrian-Horia Dediu Crochemore, M. Iliopoulos, Costas Kubica, M. Radoszewski, J. Rytter, W. Walen, T. |
| author_sort | Crochemore, M. |
| building | Curtin Institutional Repository |
| collection | Online Access |
| description | A run is an inclusion maximal occurrence in a string (as a subinterval) of a repetition v with a period p such that 2p =|v|.The maximal number of runs in a string of length n has been thoroughly studied, and is known to be between 0.944 n and 1.029 n.In this paper we investigate cubic runs, in which the shortest period p satis?es 3p =|v|. We show the upper bound of 0.5 n on the maximal number of such runs in a string of length n, and construct an in?nite sequence of words over binary alphabet for which the lower bound is 0.406 n. |
| first_indexed | 2025-11-14T09:27:06Z |
| format | Conference Paper |
| id | curtin-20.500.11937-45763 |
| institution | Curtin University Malaysia |
| institution_category | Local University |
| last_indexed | 2025-11-14T09:27:06Z |
| publishDate | 2010 |
| publisher | Springer |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | curtin-20.500.11937-457632023-01-18T08:46:45Z On the maximal number of cubic runs in a string Crochemore, M. Iliopoulos, Costas Kubica, M. Radoszewski, J. Rytter, W. Walen, T. Adrian-Horia Dediu Henning Fernau Carlos Martin-Vide A run is an inclusion maximal occurrence in a string (as a subinterval) of a repetition v with a period p such that 2p =|v|.The maximal number of runs in a string of length n has been thoroughly studied, and is known to be between 0.944 n and 1.029 n.In this paper we investigate cubic runs, in which the shortest period p satis?es 3p =|v|. We show the upper bound of 0.5 n on the maximal number of such runs in a string of length n, and construct an in?nite sequence of words over binary alphabet for which the lower bound is 0.406 n. 2010 Conference Paper http://hdl.handle.net/20.500.11937/45763 10.1007/978-3-642-13089-2_19 http://www.springerlink.com/content/73w55281j86r8w18 Springer restricted |
| spellingShingle | Crochemore, M. Iliopoulos, Costas Kubica, M. Radoszewski, J. Rytter, W. Walen, T. On the maximal number of cubic runs in a string |
| title | On the maximal number of cubic runs in a string |
| title_full | On the maximal number of cubic runs in a string |
| title_fullStr | On the maximal number of cubic runs in a string |
| title_full_unstemmed | On the maximal number of cubic runs in a string |
| title_short | On the maximal number of cubic runs in a string |
| title_sort | on the maximal number of cubic runs in a string |
| url | http://www.springerlink.com/content/73w55281j86r8w18 http://hdl.handle.net/20.500.11937/45763 |