文章基本信息

标题：An Optimal O(log log n) Time Parallel Algorithm for Detecting all Squares in a String
本地全文：下载
作者：Alberto Apostolico ; Dany Breslauer
期刊名称：BRICS Report Series
印刷版ISSN：0909-0878
出版年度：1995
卷号：2
期号：11
出版社：Aarhus University
摘要：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(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.