The MathNet Korea
Information Center for Mathematical Science

논문검색

Information Center for Mathematical Science

논문검색

SIAM Journal on Computing
( Vol. 25 NO.6 / (1996))
An Optimal $O(\log \log N)$-Time Parallel Algorithm for Detecting All Squares in a String
Alberto Apostolico, Dany Breslauer,
Pages. 1318-1331
Abstract
Contents 1. Introduction
2. The CRCW PRAM model
3. Testing if a string is square-free
3.1. The stages
4. Detecting all squares
4.1. The stages
5. The lower bound
6. The number of processors
7. Concluding remarks
Key words squares, repotitions, string matching, parallel algorithms, lower bounds.
Mathmatical Subject Classification 68Q10, 68Q20, 68Q25