Date: Thu, 26 Jun 2003 12:17:40 -0400 From: Christopher Weimann <csw@k12hq.com> To: freebsd-hackers@FreeBSD.org, David Schultz <das@FreeBSD.ORG>, Sean Farley <sean-freebsd@farley.org> Subject: Re: Replacing GNU grep revisited Message-ID: <20030626121740.A84048@smtp.k12us.com> In-Reply-To: <20030626064350.GB94891@HAL9000.homeunix.com>; from das@FreeBSD.ORG on Wed, Jun 25, 2003 at 11:43:50PM -0700 References: <20030621103502.K18572@thor.farley.org> <20030625000344.A54424@smtp.k12us.com> <20030625132648.J72955@thor.farley.org> <20030626064350.GB94891@HAL9000.homeunix.com>
next in thread | previous in thread | raw e-mail | index | archive | help
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! ------------------------------------------------------------
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20030626121740.A84048>