Computing String Covers in Sublinear Time
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910616704253952 |
|---|---|
| author | Radoszewski, Jakub Zuba, Wiktor |
| author_facet | Radoszewski, Jakub Zuba, Wiktor |
| contents | Let $T$ be a string of length $n$ over an integer alphabet of size $σ$. In the word RAM model, $T$ can be represented in $O(n /\log_σn)$ space. We show that a representation of all covers of $T$ can be computed in the optimal $O(n/\log_σn)$ time; in particular, the shortest cover can be computed within this time. We also design an $O(n(\logσ+ \log \log n)/\log n)$-sized data structure that computes in $O(1)$ time any element of the so-called (shortest) cover array of $T$, that is, the length of the shortest cover of any given prefix of $T$. As a by-product, we describe the structure of cover arrays of Fibonacci strings. On the negative side, we show that the shortest cover of a length-$n$ string cannot be computed using $o(n/\log n)$ operations in the PILLAR model of Charalampopoulos, Kociumaka, and Wellnitz (FOCS 2020). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_14559 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Computing String Covers in Sublinear Time Radoszewski, Jakub Zuba, Wiktor Data Structures and Algorithms Let $T$ be a string of length $n$ over an integer alphabet of size $σ$. In the word RAM model, $T$ can be represented in $O(n /\log_σn)$ space. We show that a representation of all covers of $T$ can be computed in the optimal $O(n/\log_σn)$ time; in particular, the shortest cover can be computed within this time. We also design an $O(n(\logσ+ \log \log n)/\log n)$-sized data structure that computes in $O(1)$ time any element of the so-called (shortest) cover array of $T$, that is, the length of the shortest cover of any given prefix of $T$. As a by-product, we describe the structure of cover arrays of Fibonacci strings. On the negative side, we show that the shortest cover of a length-$n$ string cannot be computed using $o(n/\log n)$ operations in the PILLAR model of Charalampopoulos, Kociumaka, and Wellnitz (FOCS 2020). |
| title | Computing String Covers in Sublinear Time |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2409.14559 |