| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 428997 | Information Processing Letters | 2012 | 4 Pages |
Abstract
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(n4logN) time and O(n2)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)O(c4log5N) time and O(c2log2N)O(c2log2N) space, which is faster than using the algorithm by Ga̧sieniec, Karpinski, Plandowski, and Rytter (1996) [4].
► Simple algorithm for square-freeness testing on compressed texts. ► Asymptotically faster than previous methods. ► Describes conversion from arbitrary composition system to small SLPs.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Hideo Bannai, Travis Gagie, Tomohiro I, Shunsuke Inenaga, Gad M. Landau, Moshe Lewenstein,