TY - JOUR

T1 - An efficient algorithm to test square-freeness of strings compressed by straight-line programs

AU - Bannai, Hideo

AU - Gagie, Travis

AU - I, Tomohiro

AU - Inenaga, Shunsuke

AU - Landau, Gad M.

AU - Lewenstein, Moshe

N1 - Funding Information:
1Partially supported by the National Science Foundation Award 0904246, Israel Science Foundation grant 347/09, Grant No. 2008217 from the United States–Israel Binational Science Foundation (BSF) and DFG.

PY - 2012/10/15

Y1 - 2012/10/15

N2 - We give a simple algorithm that, given a straight-line program of size n for a string S of length N, tests whether S is square-free in O(n 4logN) time and O(n2) space. The algorithm also allows us to test square-freeness on an arbitrary composition system of size c for S, in O(c4log5N) time and O(c2log2N) space, which is faster than using the algorithm by Ga̧sieniec, Karpinski, Plandowski, and Rytter (1996) [4].

AB - We give a simple algorithm that, given a straight-line program of size n for a string S of length N, tests whether S is square-free in O(n 4logN) time and O(n2) space. The algorithm also allows us to test square-freeness on an arbitrary composition system of size c for S, in O(c4log5N) time and O(c2log2N) space, which is faster than using the algorithm by Ga̧sieniec, Karpinski, Plandowski, and Rytter (1996) [4].

UR - http://www.scopus.com/inward/record.url?scp=84864150942&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84864150942&partnerID=8YFLogxK

U2 - 10.1016/j.ipl.2012.06.017

DO - 10.1016/j.ipl.2012.06.017

M3 - Article

AN - SCOPUS:84864150942

SN - 0020-0190

VL - 112

SP - 711

EP - 714

JO - Information Processing Letters

JF - Information Processing Letters

IS - 19

ER -