A STRING-MATCHING ALGORITHM FOR THE CREW PRAM

Authors
DEALMEIDA NF BARBOSA VC
Citation
Nf. Dealmeida et Vc. Barbosa, A STRING-MATCHING ALGORITHM FOR THE CREW PRAM, Information processing letters, 47(5), 1993, pp. 257-259
Citations number
9
Categorie Soggetti
Information Science & Library Science","Computer Applications & Cybernetics
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
47
Issue
5
Year of publication
1993
Pages
257 - 259
Database
ISI
SICI code
0020-0190(1993)47:5<257:ASAFTC>2.0.ZU;2-N
Abstract
We present an algorithm for the CREW PRAM to find all occurrences of a pattern of size m in a text of size n. For a fixed alphabet and m = O (log2 n), the algorithm runs in O(log m) time on O(n/log m) processors . Under these restrictions, it is optimal and improves on the time com plexity of previously known string-matching algorithms for the CREW PR AM.