An Optimal $O(\log \log N)$-Time Parallel Algorithm for Detecting all Squares in a String
From MaRDI portal
Publication:5691298
DOI10.1137/S0097539793260404zbMath0864.68045MaRDI QIDQ5691298
Dany Breslauer, Alberto Apostolico
Publication date: 24 February 1997
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Distributed algorithms (68W15)
Related Items (13)
Transforming comparison model lower bounds to the parallel-random-access-machine ⋮ Finding all periods and initial palindromes of a string in parallel ⋮ An efficient algorithm for online square detection ⋮ Online Detection of Repetitions with Backtracking ⋮ Efficient string matching on packed texts ⋮ An efficient algorithm to test square-freeness of strings compressed by straight-line programs ⋮ Approximate periods of strings ⋮ Optimal parallel algorithms for periods, palindromes and squares ⋮ Detecting regularities on grammar-compressed strings ⋮ Fibonacci arrays and their two-dimensional repetitions ⋮ Optimal discovery of repetitions in 2D ⋮ Optimal Parallel Searching an Array for Certain Repetitions ⋮ Repetitions detection on a linear array with reconfigurable pipelined bus system
This page was built for publication: An Optimal $O(\log \log N)$-Time Parallel Algorithm for Detecting all Squares in a String
