2008/01/01 by Wataru Matsubara, Shunsuke Inenaga, Matsubara, Wataru +3
Computer Science · #Algorithms and Data Compression #Complexity and Algorithms in Graphs #Network Packet Processing and Optimization #Square Freeness #Straight Line Program
paper · doi:10.4230/dagsemproc.08261.5
openalex publication_date 2008/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 = uk 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(n2; n log2 N))-time O(n2)-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(2n). Hence no decompress-then-test approaches can be better than our method in the worst case.