Parallel RAM Algorithms for Factorizing Words
Parallel RAM Algorithms for Factorizing Words
复制标题
用于分解单词的并行 RAM 算法
DOI：
10.1016/0304-3975(94)90100-7
复制
发表时间：
1994
影响因子：
1.1
通讯作者：
W. F. Smyth
中科院分区：
文献类型：
--
作者：
J. Daykin;C. Iliopoulos;W. F. Smyth
提出了一种使用O （n logn）个处理器的O (logn logn) CRCW PRAM算法，用于计算无界字母表上长度为n的字的唯一Lyndon分解；这改进了Apostolico和Crochemore（1989）给出的界。此外，在固定字母的情况下，CRCW PRAM算法是最优的（线性代价），需要O （log n）个单位时间。
An O (logn log log n) CRCW PRAM algorithm using O (n log 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.