OPTIMAL PARALLEL DETECTION OF SQUARES IN STRINGS

A string w is primitive if it is not a power of another string (i.e., writing w = v(k) implies k = 1. Conversely, w is a square if w = vv, with v a primitive string. A string x is square-free if it has no nonempty substring of the form ww. It is shown that the square-freedom of a string of n symbols over an arbitrary alphabet can be tested by a CRCW PRAM with n processors in O(log n) time and linear auxiliary space. If the cardinality of the input alphabet is bounded by a constant independent of the input size, then the number of processors can be reduced to n/log n without affecting the time complexity of this strategy. The fastest sequential algorithms solve this problem O(n log n) or O(n) time, depending on whether the cardinality of the input alphabet is unbounded or bounded, and either performance is known to be optimal within its class. More elaborate constructions lead to a CRCW PRAM algorithm for detecting, within the same n-processors bounds, all positioned squares in x in time O(log n) and using linear auxiliary space. The fastest sequential algorithms solve this problem in O(n log n) time, and such a performance is known to be optimal.