TY - GEN

T1 - Factorizing a string into squares in linear time

AU - Matsuoka, Yoshiaki

AU - Inenaga, Shunsuke

AU - Bannai, Hideo

AU - Takeda, Masayuki

AU - Manea, Florin

N1 - Publisher Copyright:
© Yoshiaki Matsuoka, Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda, and Florin Manea.

PY - 2016/6/1

Y1 - 2016/6/1

N2 - 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 ω = Ω(log n). We also show an O(n + (n log2 n)/ω)-time (respectively, O(n log n)-time) algorithm to find a square factorization which contains the maximum (respectively, minimum) number of squares.

AB - 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 ω = Ω(log n). We also show an O(n + (n log2 n)/ω)-time (respectively, O(n log n)-time) algorithm to find a square factorization which contains the maximum (respectively, minimum) number of squares.

UR - http://www.scopus.com/inward/record.url?scp=85011977725&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85011977725&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.CPM.2016.27

DO - 10.4230/LIPIcs.CPM.2016.27

M3 - Conference contribution

AN - SCOPUS:85011977725

T3 - Leibniz International Proceedings in Informatics, LIPIcs

SP - 27.1-27.12

BT - 27th Annual Symposium on Combinatorial Pattern Matching, CPM 2016

A2 - Grossi, Roberto

A2 - Lewenstein, Moshe

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 27th Annual Symposium on Combinatorial Pattern Matching, CPM 2016

Y2 - 27 June 2016 through 29 June 2016

ER -