EFFICIENT PARALLEL ALGORITHMS TO TEST SQUARE-FREENESS AND FACTORIZE STRINGS

被引：21

作者：

CROCHEMORE, M ^{[1
]}

RYTTER, W ^{[1
]}

机构：

[1] UNIV WARSAW, INST INFORMAT, PL-00901 WARSAW, POLAND

来源：

INFORMATION PROCESSING LETTERS | 1991年 / 38卷 / 02期

关键词：

PARALLEL ALGORITHMS; COMBINATORIAL PROBLEMS;

D O I：

10.1016/0020-0190(91)90223-5

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

A string is square-free if it does not contain a nonempty subword of the form ww. We give an algorithm testing square-freeness of strings in log n time with n processors of a CRCW PRAM. The input alphabet is not bounded. The best sequential time algorithm for this problem takes O(n log n) time. Hence the total number of operations in our parallel algorithm matches that of the best sequential algorithm. The algorithm relies on an efficient parallel computation of a factorization of words used in text compression.

引用

页码：57 / 60

页数：4

共 14 条

[1] PARALLEL CONSTRUCTION OF A SUFFIX TREE WITH APPLICATIONS [J].

APOSTOLICO, A ;

ILIOPOULOS, C ;

LANDAU, GM ;

SCHIEBER, B ;

VISHKIN, U .

ALGORITHMICA, 1988, 3 (03) :347-365

[2] OPTIMAL OFF-LINE DETECTION OF REPETITIONS IN A STRING [J].

APOSTOLICO, A ;

PREPARATA, FP .

THEORETICAL COMPUTER SCIENCE, 1983, 22 (03) :297-315

[3]

APOSTOLICO A, 1990, UNPUB OPTIMAL PARALL

[4]

Apostolico A., 1985, COMBINATORIAL ALGORI, VF12, P85

[5] TRANSDUCERS AND REPETITIONS [J].

CROCHEMORE, M .

THEORETICAL COMPUTER SCIENCE, 1986, 45 (01) :63-86

[6] AN OPTIMAL ALGORITHM FOR COMPUTING THE REPETITIONS IN A WORD [J].

CROCHEMORE, M .

INFORMATION PROCESSING LETTERS, 1981, 12 (05) :244-250

[7]

CROCHEMORE M, 1990, LECT NOTES COMPUT SC, V415, P109

[8]

CROCHEMORE M, 1989, LECT NOTES COMPUT SC, V377, P1

[9]

Gibbons A., 1988, EF FICIENT PARALLEL

[10]

Lothaire M., 1983, COMBINATORICS WORDS

← 1 2 →