License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.08261.5
URN: urn:nbn:de:0030-drops-16804
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2008/1680/
Go to the corresponding Portal |
Matsubara, Wataru ;
Inenaga, Shunsuke ;
Shinohara, Ayumi
An Efficient Algorithm to Test Square-Freeness 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
square-free if no substrings of w are squares. Many efficient algorithms
to test if a given string is square-free, have been developed so far. However,
very little is known for testing square-freeness 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 square-freeness 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 decompress-then-test
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 Square-Freeness of Strings Compressed by Balanced Straight Line Program}},
booktitle = {Structure-Based Compression of Complex Massive Data},
series = {Dagstuhl Seminar Proceedings (DagSemProc)},
ISSN = {1862-4405},
year = {2008},
volume = {8261},
editor = {Stefan B\"{o}ttcher and Markus Lohrey and Sebastian Maneth and Wojcieh Rytter},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2008/1680},
URN = {urn:nbn:de:0030-drops-16804},
doi = {10.4230/DagSemProc.08261.5},
annote = {Keywords: Square Freeness, Straight Line Program}
}
Keywords: |
|
Square Freeness, Straight Line Program |
Collection: |
|
08261 - Structure-Based Compression of Complex Massive Data |
Issue Date: |
|
2008 |
Date of publication: |
|
20.11.2008 |