An optimal O(log log n) time parallel string matching algorithm. (English) Zbl 0711.68057

Breslauer, Dany; Galil, Zvi

SIAM J. Comput. 19, No. 6, 1051-1058 (1990).

Summary: An optimal O(log log n) time parallel algorithm for string matching on CRCW-PRAM is presented. It improves previous results of Z. Galil [Inf. Control 67, 144-157 (1985; Zbl 0588.68022)] and U. Vishkin [ibid. 67, 91-113 (1985; Zbl 0588.68023)].

MSC:

68Q25	Analysis of algorithms and problem complexity
68Q10	Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68W10	Parallel algorithms in computer science

Keywords:

period; parallel algorithm; string

Citations:

Zbl 0588.68022; Zbl 0588.68023