Re: Replacing GNU grep revisited

From: Christopher Weimann (csw_at_k12hq.com)
Date: 06/26/03

  • Next message: Alan L. Cox: "Re: [hackers] Re: Page Coloring Defines in vm_page.h" 
    Date: Thu, 26 Jun 2003 12:17:40 -0400
To: freebsd-hackers@FreeBSD.org, David Schultz <das@FreeBSD.ORG>, Sean Farley <sean-freebsd@farley.org>

    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"
  • Next message: Alan L. Cox: "Re: [hackers] Re: Page Coloring Defines in vm_page.h"