文摘
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 time and space. The algorithm also allows us to test square-freeness on an arbitrary composition system of size c for S, in time and space, which is faster than using the algorithm by Ga?sieniec, Karpinski, Plandowski, and Rytter (1996) .