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 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. [References: 29]