2026-07-23T06:52:07Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:1680 2024-03-06T11:08:09Z ddc:004 open_access

An Efficient Algorithm to Test Square-Freeness of Strings Compressed by Balanced Straight Line Program Matsubara, Wataru Inenaga, Shunsuke Shinohara, Ayumi Square Freeness Straight Line Program In this paper we study the problem of deciding whether a given compressed string contains a square. A string x is called a square if x = zz and z = u^k implies k = 1 and u = z. A string w is said to be square-free if no substrings of w are squares. Many efficient algorithms to test if a given string is square-free, have been developed so far. However, very little is known for testing square-freeness of a given compressed string. In this paper, we give an O(max(n^2; n log^2 N))-time O(n^2)-space solution to test square-freeness of a given compressed string, where n and N are the size of a given compressed string and the corresponding decompressed string, respectively. Our input strings are compressed by balanced straight line program (BSLP). We remark that BSLP has exponential compression, that is, N = O(2^n). Hence no decompress-then-test approaches can be better than our method in the worst case. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Wataru Matsubara and Shunsuke Inenaga and Ayumi Shinohara 2008 Is Part Of Dagstuhl Seminar Proceedings, Volume 8261, Structure-Based Compression of Complex Massive Data (2008) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/DagSemProc.08261.5 urn:nbn:de:0030-drops-16804 https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08261.5 eng https://creativecommons.org/licenses/by/4.0/legalcode