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 possible optimal algorithm. When p processors are available, the bounds become Theta(inverted right perpendicular n log n)/p inverted left perpendicular + log log(interverted right perpendicular 1+p/n interverted left perpendicular) 2p). The algorithm uses an optimal parallel string-matching algorithm together with periodicity properties to locate the squares within the input string.