2026-08-16T02:50:18Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6064 2024-03-06T10:37:36Z ddc:004 open_access

Factorizing a String into Squares in Linear Time Matsuoka, Yoshiaki Inenaga, Shunsuke Bannai, Hideo Takeda, Masayuki Manea, Florin Squares Runs Factorization of Strings 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yoshiaki Matsuoka and Shunsuke Inenaga and Hideo Bannai and Masayuki Takeda and Florin Manea 2016 Is Part Of LIPIcs, Volume 54, 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2016.27 urn:nbn:de:0030-drops-60645 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2016.27 eng https://creativecommons.org/licenses/by/3.0/legalcode