[comp.lang.pascal] Dynamic string matching - O

hsu_wh@jhunix.HCF.JHU.EDU (William H Hsu) (09/10/90)

     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