Name
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 = uk 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(n2,n log2 N))-time O(n2)-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(2n). Hence no decompress-then-test approaches can be better than our method in the worst case. |
Year | Venue | Keywords |
|---|---|---|
2009 | CATS | string w,exponential compression,log2 n,decompress-then-test approach,time o,input string,corresponding decompressed string,balanced straight line program,efficient algorithm,testing square-freeness,space solution |
Field | DocType | Citations |
String searching algorithm,Discrete mathematics,Combinatorics,Commentz-Walter algorithm,Empty string,Computer science,Approximate string matching,Compressed suffix array,String metric,String (computer science),Boyer–Moore string search algorithm | Conference | 1 |
PageRank | References | Authors |
0.37 | 16 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Wataru Matsubara | 1 | 52 | 5.87 |
| Shunsuke Inenaga | 2 | 595 | 79.02 |
| Ayumi Shinohara | 3 | 936 | 88.28 |