Derivation of a parallel string matching algorithm

被引：5

作者：

Misra, J ^{[1
]}

机构：

[1] Univ Texas, Austin, TX 78712 USA

来源：

INFORMATION PROCESSING LETTERS | 2003年 / 85卷 / 05期

关键词：

parallel algorithms; string; data structures; powerlist;

D O I：

10.1016/S0020-0190(02)00416-7

中图分类号：

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

学科分类号：

0812 ;

摘要：

We derive an efficient parallel algorithm to find all occurrences of a pattern string in a subject string in O(log n) time, where n is the length of the subject string. The number of processors employed is of the order of the product of the two string lengths. The theory of powerlists [J. Kornerup, PhD Thesis, 1997; J. Misra, ACM Trans. Programming Languages Systems 16 (16) (1994) 1737-1740] is central to the development of the algorithm and its algebraic manipulations. (C) 2002 Elsevier Science B.V. All rights reserved.

引用

页码：255 / 260

页数：6