Xref: utzoo comp.lang.c:30362 comp.lang.pascal:3812 comp.sys.mac.wanted:532
Path: utzoo!attcan!uunet!cs.utexas.edu!sdd.hp.com!uakari.primate.wisc.edu!aplcen!jhunix!hsu_wh
From: hsu_wh@jhunix.HCF.JHU.EDU (William H Hsu)
Newsgroups: comp.lang.c,comp.lang.pascal,comp.sys.mac.wanted
Subject: String matching - parallel/concurrent/randomized info needed
Keywords: string, match, parallel, random, info, help
Message-ID: <5855@jhunix.HCF.JHU.EDU>
Date: 18 Jul 90 14:26:44 GMT
Followup-To: poster
Organization: The Johns Hopkins University - HCF
Lines: 30


     I am trying to implement some good partial string matching
functions for use with strictly binary files (specifically, the
resource forks of Macintosh files).  I have encountered several
compiler and language specific problems while trying to get two
algorithms (one generic dynamic pattern matching scheme and one
randomized version of the Boyer-Moore/BMG algorithm) to work in
C.  
     First, I'm looking for a way to parallelize my string
matching.  I have seen references to a concurrent version of
Boyer-Moore and dynamic algorithms that run in O(kn) time for k-
approximate matches in text length n (Landau and Vishkin, 18th
Annual ACM Symposium), but have been unable to get my hands on
real or pseudocode.  Since I am looking for 10-100 short, random
strings, it would boost my program efficiency greatly to be able
to search for multiple patterns at once.  Has anyone implemented
a concurrent version of BMG or a dynamic partial-matching
algorithm in C (without parallel hardware)?
     Second, I'm sure that random number generation is a
universally known problem, but I have had problems using srand()
in the right place to get truly "random" pattern strings.  rand()
is used to generate the starting location for the source string. 
But I frequently get consecutive duplicate strings (four or five
"two in a row" strings per hundred).  My randomization call is:
     srand((unsigned)time(NULL));
How can the "randomness" be improved?  I have observed that
moving the line deeper into my nested while/for loops causes a
decrease in randomness.
     Please E-mail responses to: hsu_wh@jhunix.hcf.jhu.edu
(BITNET), hsu@cs.jhu.edu (ARPAnet)