An Optimal O(log log n) Time Parallel Algorithm for Detecting all Squares in a String
AbstractAn 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(n log n / p + log log 2p). The algorithm uses an optimal parallel
string-matching algorithm together with periodicity properties to locate
the squares within the input string.
How to Cite
Apostolico, A., & Breslauer, D. (1995). An Optimal O(log log n) Time Parallel Algorithm for Detecting all Squares in a String. BRICS Report Series, 2(11). https://doi.org/10.7146/brics.v2i11.19514
Articles published in DAIMI PB are licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.