An Optimal Time Parallel Algorithm for Detecting all
Squares in a String
An optimal 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 . The algorithm uses an optimal parallel string-matching algorithm together with periodicity properties to locate the squares within the input string.