Simple Linear-time Repetition Factorization
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916350475108352 |
|---|---|
| author | Yonemoto, Yuki Inenaga, Shunsuke |
| author_facet | Yonemoto, Yuki Inenaga, Shunsuke |
| contents | A factorization $f_1, \ldots, f_m$ of a string $w$ of length $n$ is called a repetition factorization of $w$ if $f_i$ is a repetition, i.e., $f_i$ is a form of $x^kx'$, where $x$ is a non-empty string, $x'$ is a (possibly-empty) proper prefix of $x$, and $k \geq 2$. Dumitran et al. [SPIRE 2015] presented an $O(n)$-time and space algorithm for computing an arbitrary repetition factorization of a given string of length $n$. Their algorithm heavily relies on the Union-Find data structure on trees proposed by Gabow and Tarjan [JCSS 1985] that works in linear time on the word RAM model, and an interval stabbing data structure of Schmidt [ISAAC 2009]. In this paper, we explore more combinatorial insights into the problem, and present a simple algorithm to compute an arbitrary repetition factorization of a given string of length $n$ in $O(n)$ time, without relying on data structures for Union-Find and interval stabbing. Our algorithm follows the approach by Inoue et al. [ToCS 2022] that computes the smallest/largest repetition factorization in $O(n \log n)$ time. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_04253 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Simple Linear-time Repetition Factorization Yonemoto, Yuki Inenaga, Shunsuke Data Structures and Algorithms A factorization $f_1, \ldots, f_m$ of a string $w$ of length $n$ is called a repetition factorization of $w$ if $f_i$ is a repetition, i.e., $f_i$ is a form of $x^kx'$, where $x$ is a non-empty string, $x'$ is a (possibly-empty) proper prefix of $x$, and $k \geq 2$. Dumitran et al. [SPIRE 2015] presented an $O(n)$-time and space algorithm for computing an arbitrary repetition factorization of a given string of length $n$. Their algorithm heavily relies on the Union-Find data structure on trees proposed by Gabow and Tarjan [JCSS 1985] that works in linear time on the word RAM model, and an interval stabbing data structure of Schmidt [ISAAC 2009]. In this paper, we explore more combinatorial insights into the problem, and present a simple algorithm to compute an arbitrary repetition factorization of a given string of length $n$ in $O(n)$ time, without relying on data structures for Union-Find and interval stabbing. Our algorithm follows the approach by Inoue et al. [ToCS 2022] that computes the smallest/largest repetition factorization in $O(n \log n)$ time. |
| title | Simple Linear-time Repetition Factorization |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2408.04253 |