Parallel Detection of all Palindromes in a String

Parallel Detection of all Palindromes in a String
复制标题

字符串中所有回文的并行检测

DOI：
10.1007/3-540-57785-8_166
复制
发表时间：
1994
期刊：
--
影响因子：
--
通讯作者：
Z. Galil
Z. Galil
中科院分区：
--
文献类型：
--
作者：
A. Apostolico;Dany Breslauer;Z. Galil

文献摘要

被引文献

相似文献

本文提出了两种高效的并发读并发写并行算法，它们可以找到给定字符串中的所有回文：1.通用字母表上的ANO(LogN)时间、n处理器算法。在字母表大小固定的情况下，该算法只需要n/logn个处理器，从而获得了最佳的加速比。2.在一般字母表上，Ano(Loglogn)时间，nlogn/loglogn-处理器算法。这些新的结果改进了已知的并行回文检测算法，使用了更小的辅助空间，或者通过进行更少的操作，或者通过获得更快的运行时间。
This paper presents two efficient concurrent-read concurrent-write parallel algorithms that find all palindromes in a given string:1.AnO(logn) time, n-processor algorithm over general alphabets. In case of constant size alphabets the algorithm requires only n/log n processors, and thus achieves an optimal-speedup.2.AnO(log logn) time,nlogn/loglog n-processor algorithm over general alphabets. This is the fastest possible time with the number of processors used.These new results improve on the known parallel palindrome detection algorithms by using smaller auxiliary space and either by making fewer operations or by achieving a faster running time.