Name
Abstract | ||
|---|---|---|
A factorization f1,…,fm of a string w is called a repetition factorization of w if each factor fi is a repetition, namely,
$f_{i} = x^{k}x^{\prime }$
for some non-empty string x, an integer k ≥ 2, and
$x^{\prime }$
being a proper prefix of x. Dumitran et al. (Proc. SPIRE 2015) proposed an algorithm which computes an arbitrary repetition factorization of a given string w in O(n) time, where n is the length of w. The number of factors (i.e. repetitions) contained in the output of their algorithm is not known or guaranteed. In this paper, we propose two algorithms for computing smallest/largest repetition factorizations in
$O(n \log n)$
time, which respectively consist of the smallest/largest number of factors. The first algorithm is a simple
$O(n \log n)$
-space algorithm based on a reduction of the problem to the shortest/longest path problem on the DAG of size
$O(n \log n)$
. The second one simulates the dynamic programming algorithm for shortest/longest path problem within O(n) space based on the idea of the first algorithm. Moreover, we discuss combinatorial structures of smallest/largest repetition factorizations of Fibonacci strings. |
Year | DOI | Venue |
|---|---|---|
2022 | 10.1007/s00224-022-10070-3 | Theory of Computing Systems |
Keywords | DocType | Volume |
Repetition factorizations, Squares, Dynamic programming, Fibonacci strings | Journal | 66 |
Issue | ISSN | Citations |
2 | 1432-4350 | 0 |
PageRank | References | Authors |
0.34 | 13 | 6 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hiroe Inoue | 1 | 0 | 0.34 |
| Yoshiaki Matsuoka | 2 | 2 | 1.07 |
| Yuto Nakashima | 3 | 0 | 1.35 |
| Shunsuke Inenaga | 4 | 595 | 79.02 |
| Hideo Bannai | 5 | 620 | 79.87 |
| Masayuki Takeda | 6 | 9 | 13.78 |