An Efficient Algorithm to Test SquareFreeness of Strings Compressed by Balanced Straight Line Program

Structure-Based Compression of Complex Massive Data

计算机科学;物理学

Wataru Matsubara1, Shunsuke Inenaga2, and Ayumi Shinohara1 ; 2 Graduate School of Information Science ; Electrical Engineering

PID  :  82135

学科分类：计算机科学（综合）

来源: CEUR

【 摘 要 】

In this paper we study the problem of deciding whether agiven 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 squarefree if no substrings of w are squares. Many efficient algorithms to test if a given string is squarefree, have been developed so far. How ever, very little is known for testing squarefreeness of a given compressed string. In this paper, we give an O(max(n2, n log2N))time O(n2)space solution to test squarefreeness 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 expo nential compression, that is, N = O(2n). Hence no decompressthentest