[prev in list] [next in list] [prev in thread] [next in thread] 

List:       freebsd-hackers
Subject:    Re: Replacing GNU grep revisited
From:       Christopher Weimann <csw () k12hq ! com>
Date:       2003-06-26 16:17:40
[Download RAW message or body]

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!
------------------------------------------------------------

_______________________________________________
freebsd-hackers@freebsd.org mailing list
http://lists.freebsd.org/mailman/listinfo/freebsd-hackers
To unsubscribe, send any mail to "freebsd-hackers-unsubscribe@freebsd.org"
[prev in list] [next in list] [prev in thread] [next in thread]