An Optimal tex2html_wrap_inline22 Time Parallel Algorithm for Detecting all Squares in a String

Alberto Apostolico
Dany Breslauer

February 1995

Abstract:

An optimal tex2html_wrap_inline22 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 tex2html_wrap_inline28. The algorithm uses an optimal parallel string-matching algorithm together with periodicity properties to locate the squares within the input string.

Available as PostScript, PDF, DVI.

 

Last modified: 2003-06-08 by webmaster.