{'fraction_non_alphanumeric': 0.044790652385589096, 'fraction_numerical': 0.004868549172346641, 'mean_word_length': 4.03921568627451, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
An Efficient Algorithm to Test Square-Freeness of Strings Compressed by Balanced Straight Line Programs

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.