An Optimal O(log log n) Time Parallel Algorithm for Detecting all Squares in a String
Copyright policy )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<br />algorithm for detecting all squares in a string is presented. A tight<br />lower bound shows that over general alphabets this is the fastest possible<br />optimal algorithm. When p processors are available the bounds become<br />Theta(n log n / p + log log 2p). The algorithm uses an optimal parallel<br />string-matching algorithm together with periodicity properties to locate<br />the squares within the input string.
- Purdue University System United States
- University of Padua Italy
- Purdue University West Lafayette United States
parallel string-matching algorithm, Computer Sciences, Analysis of algorithms and problem complexity, Distributed algorithms, Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
parallel string-matching algorithm, Computer Sciences, Analysis of algorithms and problem complexity, Distributed algorithms, Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).14 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Top 10% impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!