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 -