Name
Abstract | ||
|---|---|---|
A square factorization of a string w is a factorization of w in which each factor is a square. Dumitran et al. [SPIRE 2015, pp. 54-66] showed how to find a square factorization of a given string of length n in O(n log n) time, and they posed a question whether it can be done in O(n) time. In this paper, we answer their question positively, showing an O(n)-time algorithm for square factorization in the standard word RAM model with machine word size omega = Omega(log n). We also show an O(n + (n log^2 n) / omega)-time (respectively, O(n log n)-time) algorithm to find a square factorization which contains the maximum (respectively, minimum) number of squares. |
Year | Venue | Field |
|---|---|---|
2016 | CPM | Discrete mathematics,Binary logarithm,Combinatorics,Word ram,Omega,Factorization,Dixon's factorization method,Time complexity,Word (computer architecture),Mathematics,Quadratic sieve |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
0 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yoshiaki Matsuoka | 1 | 0 | 0.68 |
| Shunsuke Inenaga | 2 | 595 | 79.02 |
| Hideo Bannai | 3 | 620 | 79.87 |
| Masayuki Takeda | 4 | 902 | 79.24 |
| Florin Manea | 5 | 372 | 58.12 |