AN OPTIMAL O(LOG LOG N)-TIME PARALLEL ALGORITHM FOR DETECTING ALL SQUARES IN A STRING

An optimal O(log log n)-time concurrent-read concurrent-write parallel algorithm for detecting all squares in a string is presented. A tight lower bound shows that over general alphabets, this is the fastest po ssible optimal algorithm. When p processors are available, the bounds become Theta(inverted right perpendicular n log n)/p inverted left per pendicular + log log(interverted right perpendicular 1+p/n interverted left perpendicular) 2p). The algorithm uses an optimal parallel strin g-matching algorithm together with periodicity properties to locate th e squares within the input string.