A CONSTANT-TIME OPTIMAL PARALLEL STRING-MATCHING ALGORITHM

被引：16

作者：

GALIL, Z ^{[1
]}

机构：

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

来源：

JOURNAL OF THE ASSOCIATION FOR COMPUTING MACHINERY | 1995年 / 42卷 / 04期

关键词：

CONSTANT TIME; CRCW-PRAM; LION HUNTING; OPTIMAL PARALLEL ALGORITHM; PERIOD; STRING MATCHING;

D O I：

10.1145/210332.210341

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

Given a pattern string, we describe a way to preprocess it. We design a CRCW-PRAM constant-time optimal parallel algorithm for finding all occurrences of the (preprocessed) pattern in any given text.

引用

页码：908 / 918

页数：11

共 19 条

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

BRENT, RP .

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

[2] AN OPTIMAL O(LOG LOG-N) TIME PARALLEL STRING MATCHING ALGORITHM [J].

BRESLAUER, D ;

GALIL, Z .

SIAM JOURNAL ON COMPUTING, 1990, 19 (06) :1051-1058

[3]

BRESLAUER D, 1991, 23RD P ACM S THEOR C, P439

[4]

COLE R, 1993, AN S FDN CO, P248

[5] UPPER AND LOWER TIME-BOUNDS FOR PARALLEL RANDOM-ACCESS MACHINES WITHOUT SIMULTANEOUS WRITES [J].

COOK, S ;

DWORK, C ;

REISCHUK, R .

SIAM JOURNAL ON COMPUTING, 1986, 15 (01) :87-97

[6]

CZUMAJ A, 1995, IN PRESS 26TH P ANN

[7]

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

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

GALIL, Z .

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

[9]

Karp R. M., 1972, PROC 4 ANN ACM S THE, P125

[10] EFFICIENT RANDOMIZED PATTERN-MATCHING ALGORITHMS [J].

KARP, RM ;

RABIN, MO .

IBM JOURNAL OF RESEARCH AND DEVELOPMENT, 1987, 31 (02) :249-260

← 1 2 →