TY - GEN
T1 - Testing square-freeness of strings compressed by balanced straight line program
AU - Matsubara, Wataru
AU - Inenaga, Shunsuke
AU - Shinohara, Ayumi
PY - 2009
Y1 - 2009
N2 - 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.
AB - 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.
KW - Balanced straight line program
KW - Repetitions
KW - Squares
KW - String algorithm
KW - Text compression
UR - http://www.scopus.com/inward/record.url?scp=84859645349&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84859645349&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:84859645349
SN - 9781920682750
T3 - Conferences in Research and Practice in Information Technology Series
BT - Theory of Computing 2009 - Proceedings of the Fifteenth Computing
T2 - Theory of Computing 2009 - 15th Computing: The Australasian Theory Symposium, CATS 2009
Y2 - 20 January 2009 through 23 January 2009
ER -