AN OPTIMAL O(LOG LOG-N) TIME PARALLEL STRING MATCHING ALGORITHM

被引：41

作者：

BRESLAUER, D ^{[1
]}

GALIL, Z ^{[1
]}

机构：

[1] TEL AVIV UNIV,IL-69978 TEL AVIV,ISRAEL

来源：

SIAM JOURNAL ON COMPUTING | 1990年 / 19卷 / 06期

关键词：

D O I：

10.1137/0219072

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

An optimal O(log log n) time parallel algorithm for string matching on CRCW-PRAM is presented. It improves previous results of Galil [Inform. and Control, 67 (1985), pp. 144-157] and Vishkin [Inform. and Control, 67 (1985), pp.91-113].

引用

页码：1051 / 1058

页数：8

共 15 条

[1]

BEAME P, 1987, 19TH P ACM S THEOR C, P83

[2]

BERKMAN O, 1988, SOME DOUBLY LOGARITH

[3] ROUTING, MERGING, AND SORTING ON PARALLEL MODELS OF COMPUTATION [J].

BORODIN, A ;

HOPCROFT, JE .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1985, 30 (01) :130-145

[4] FAST STRING SEARCHING ALGORITHM [J].

BOYER, RS ;

MOORE, JS .

COMMUNICATIONS OF THE ACM, 1977, 20 (10) :762-772

[5] PARALLEL EVALUATION OF GENERAL ARITHMETIC EXPRESSIONS [J].

BRENT, RP .

JOURNAL OF THE ACM, 1974, 21 (02) :201-206

[6]

FICH FE, 1984, 3RD P ANN ACM S PRIN, P179

[7] OPTIMAL PARALLEL ALGORITHMS FOR STRING MATCHING [J].

GALIL, Z .

INFORMATION AND CONTROL, 1985, 67 (1-3) :144-157

[8]

KRUSKAL CP, 1983, IEEE T COMPUT, V32, P942, DOI 10.1109/TC.1983.1676138

[9]

Passman DS., 1962, MICH MATH J, V9, P375, DOI [10.1307/mmj/1028998773, DOI 10.1307/MMJ/1028998773]

[10]

SCHIEBER B, 1987, PARALLEL COMPLEXITY

← 1 2 →