Journal article
Parallel RAM algorithms for factorizing words
Abstract
An O(logn log log n) CRCW PRAM algorithm using O(nlog n) processors for computing the unique Lyndon factorization of a word of length n over an unbounded alphabet is presented; this improves the bounds given by Apostolico and Crochemore (1989). Moreover, in the case of fixed alphabets the CRCW PRAM algorithm is optimal (linear cost), requiring O(log n) units of time.
Authors
Daykin JW; Iliopoulos CS; Smyth WF
Journal
Theoretical Computer Science, Vol. 127, No. 1, pp. 53–67
Publisher
Elsevier
Publication Date
5 1994
DOI
10.1016/0304-3975(94)90100-7
ISSN
0304-3975