Parallel String Matching with Variable Length Don′t Cares

✍ Scribed by A.A. Bertossi; F. Logi

• Book ID: 102601717
• Publisher: Elsevier Science
• Year: 1994
• Tongue: English
• Weight: 450 KB
• Volume: 22
• Category: Article
• ISSN: 0743-7315
• DOI: 10.1006/jpdc.1994.1083

✦ Synopsis

String matching is the problem of finding all the occurrences of a pattern (P) in a text (T), where (P) and (T) are strings over a finite alphabet (\mathbf{\Sigma}). A variable length don't care is a special character, not belonging to (\Sigma), which can match any string in (\Sigma^{*}). The stringmatching problem with variable length don't cares is an extension of the classical string-matching problem in which the pattern (P) may contain an arbitrary number of don't cares. An efficient parallel algorithm is given for solving the string-matching problem with variable length don't cares. The EREW PRAM model of parallel computer with scan operations is used to obtain an (O(\log) (n) ) running time using (O(m n / \log n)) processors, where (m) and (n) are, respectively, the lengths of (P) and (T). The proposed parallel algorithm has an (\Omega(1 / \log n)) processor utilization, since the fastest serial algorithm known so far has an (O(m n / \log n)) running time. O 1994 Academic Press, Inc.