Extracting powers and periods in a word from its runs structure
A breakthrough in the field of text algorithms was the discovery of the fact that the maximal number of runs in a word of length n is O(n) and that they can all be computed in O(n) time. We study some applications of this result. New simpler O(n) time algorithms are presented for classical textual p...
| Main Authors: | , , , , , |
|---|---|
| Format: | Journal Article |
| Published: |
Elsevier
2014
|
| Online Access: | http://hdl.handle.net/20.500.11937/48986 |
| _version_ | 1848758138570801152 |
|---|---|
| author | Crochemore, M. Iliopoulos, Costas Kubica, M. Kubica, M. Radoszewski, J. Rytter, W. Walen, T. |
| author_facet | Crochemore, M. Iliopoulos, Costas Kubica, M. Kubica, M. Radoszewski, J. Rytter, W. Walen, T. |
| author_sort | Crochemore, M. |
| building | Curtin Institutional Repository |
| collection | Online Access |
| description | A breakthrough in the field of text algorithms was the discovery of the fact that the maximal number of runs in a word of length n is O(n) and that they can all be computed in O(n) time. We study some applications of this result. New simpler O(n) time algorithms are presented for classical textual problems: computing all distinct k-th word powers for a given k, in particular squares for k=2, and finding all local periods in a given word of length n. Additionally, we present an efficient algorithm for testing primitivity of factors of a word and computing their primitive roots. Applications of runs, despite their importance, are underrepresented in existing literature (approximately one page in the paper of Kolpakov and Kucherov, 1999 [25,26]). In this paper we attempt to fill in this gap. We use Lyndon words and introduce the Lyndon structure of runs as a useful tool when computing powers. In problems related to periods we use some versions of the Manhattan skyline problem. |
| first_indexed | 2025-11-14T09:39:13Z |
| format | Journal Article |
| id | curtin-20.500.11937-48986 |
| institution | Curtin University Malaysia |
| institution_category | Local University |
| last_indexed | 2025-11-14T09:39:13Z |
| publishDate | 2014 |
| publisher | Elsevier |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | curtin-20.500.11937-489862017-03-15T22:56:34Z Extracting powers and periods in a word from its runs structure Crochemore, M. Iliopoulos, Costas Kubica, M. Kubica, M. Radoszewski, J. Rytter, W. Walen, T. A breakthrough in the field of text algorithms was the discovery of the fact that the maximal number of runs in a word of length n is O(n) and that they can all be computed in O(n) time. We study some applications of this result. New simpler O(n) time algorithms are presented for classical textual problems: computing all distinct k-th word powers for a given k, in particular squares for k=2, and finding all local periods in a given word of length n. Additionally, we present an efficient algorithm for testing primitivity of factors of a word and computing their primitive roots. Applications of runs, despite their importance, are underrepresented in existing literature (approximately one page in the paper of Kolpakov and Kucherov, 1999 [25,26]). In this paper we attempt to fill in this gap. We use Lyndon words and introduce the Lyndon structure of runs as a useful tool when computing powers. In problems related to periods we use some versions of the Manhattan skyline problem. 2014 Journal Article http://hdl.handle.net/20.500.11937/48986 Elsevier restricted |
| spellingShingle | Crochemore, M. Iliopoulos, Costas Kubica, M. Kubica, M. Radoszewski, J. Rytter, W. Walen, T. Extracting powers and periods in a word from its runs structure |
| title | Extracting powers and periods in a word from its runs structure |
| title_full | Extracting powers and periods in a word from its runs structure |
| title_fullStr | Extracting powers and periods in a word from its runs structure |
| title_full_unstemmed | Extracting powers and periods in a word from its runs structure |
| title_short | Extracting powers and periods in a word from its runs structure |
| title_sort | extracting powers and periods in a word from its runs structure |
| url | http://hdl.handle.net/20.500.11937/48986 |