ONLINE AND DYNAMIC RECOGNITION OF SQUAREFREE STRINGS
Jesper Jansson, Zeshan Peng · International Journal of Foundations of Computer Science · 2007
The online squarefree recognition problem is to detect the first occurrence of a square in a string whose characters are provided as input one at a time. We present an efficient algorithm to solve this problem for strings over arbitrarily ordered alphabets in O(n log n) time, where n is the ending position of the first square. We also note that the same technique yields an O(n·(|Σn|+ log n))-time algorithm for general alphabets, where |Σn| is the number of different symbols in the first n positions of the input string. (This is faster than the previously fastest method for general alphabets when |Σn| = o( log 2 n).) Finally, we present a simple algorithm for a dynamic version of the problem over general alphabets in which we are initially given a squarefree string, followed by a series of updates, and the objective is to determine after each update if the resulting string is still squarefree.