Xref: utzoo comp.lang.c:31716 comp.lang.pascal:4065
Path: utzoo!utgpu!watserv1!watmath!att!tut.cis.ohio-state.edu!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
Subject: Dynamic string matching - O(kn) version, source needed
Keywords: dynamic string matching, source
Message-ID: <6367@jhunix.HCF.JHU.EDU>
Date: 9 Sep 90 21:30:43 GMT
Followup-To: poster
Organization: The Johns Hopkins University - HCF
Lines: 14


     I recently ran across an improved version of the dynamic
string matching algorithm described by Sara Baase in _Computer
Algorithms: Theory and Design_; it was in a paper by Landau and
Vishkin in the 18th annual ACM STOC.  Has anyone implemented the
O(kn) version in C?  I might be mistaken, but it seemed that the
earlier, non-parallel version did not require any special
hardware.  Could that be used on a PC?  Thanks.

Please E-mail responses to:

     hsu_wh@jhunix.hcf.jhu.edu (BITNET)
     hsu@cs.jhu.edu (ARPAnet)
     hsu_wh@jhuvms.hcf.jhu.edu