Matsubara, Wataru ;
Inenaga, Shunsuke ;
Shinohara, Ayumi
An Efficient Algorithm to Test SquareFreeness of Strings Compressed by Balanced Straight Line Program
Abstract
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
squarefree if no substrings of w are squares. Many efficient algorithms
to test if a given string is squarefree, have been developed so far. However,
very little is known for testing squarefreeness 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 squarefreeness 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 decompressthentest
approaches can be better than our method in the worst case.
BibTeX  Entry
@InProceedings{matsubara_et_al:DagSemProc.08261.5,
author = {Matsubara, Wataru and Inenaga, Shunsuke and Shinohara, Ayumi},
title = {{An Efficient Algorithm to Test SquareFreeness of Strings Compressed by Balanced Straight Line Program}},
booktitle = {StructureBased Compression of Complex Massive Data},
series = {Dagstuhl Seminar Proceedings (DagSemProc)},
ISSN = {18624405},
year = {2008},
volume = {8261},
editor = {Stefan B\"{o}ttcher and Markus Lohrey and Sebastian Maneth and Wojcieh Rytter},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2008/1680},
URN = {urn:nbn:de:0030drops16804},
doi = {10.4230/DagSemProc.08261.5},
annote = {Keywords: Square Freeness, Straight Line Program}
}
20.11.2008
Keywords: 

Square Freeness, Straight Line Program 
Seminar: 

08261  StructureBased Compression of Complex Massive Data

Issue date: 

2008 
Date of publication: 

20.11.2008 