Replacing GNU grep revisited

[Christopher Weimann]

On Wed 06/25/2003-11:43:50PM -0700, David Schultz wrote:
> 
> The only good string matching algorithm I actually understand is
> KMP, but really smart people tell me Boyer-Moore is the fastest in
> the average case.  It *can* be worse than KMP, depending on the
> input, but for nearly all inputs it supposedly works quite well.
> There shouldn't be any patent issues associated with it.

Aho-Corasick and Commentz-Walter specifically deal with searching
for multiple keywords which is really a different problem than
searching for a single keyword like KMP or Boyer-Moore.  

Here is a neat applet that shows how AC works.
http://www-sr.informatik.uni-tuebingen.de/~buehler/AC/AC.html

-- 
------------------------------------------------------------
Christopher Weimann
http://www.k12usa.com
K12USA.com Cool Tools for Schools!
------------------------------------------------------------