Path: utzoo!utgpu!news-server.csri.toronto.edu!bonnie.concordia.ca!uunet!comp.vuw.ac.nz!actrix!templar!jbickers
From: jbickers@templar.actrix.gen.nz (John Bickers)
Newsgroups: comp.sys.amiga.programmer
Subject: Re: The Boyer-Moore string searching algorithm
Message-ID: <4418.tnews@templar.actrix.gen.nz>
Date: 13 Jun 91 08:02:48 GMT
References: <492@regina.uregina.ca> <19453c80.ARN360b@moria.uucp> <1991Jun10.140028.9664@ira.uka.de> <1947e763.ARN36eb@moria.uucp> <1991Jun12.143556.4127@ira.uka.de>
Organization: TAP, NZAmigaUG.
Lines: 16

Quoted from <1991Jun12.143556.4127@ira.uka.de> by S_ASCHMIDT@iravcl.ira.uka.de (|S| Angela Schmidt):

> > I'm sorry, but I believe Boyer-Moore is O(m+n) like KMP.  But Boyer-Moore has

> Sorry, but I'm *very* shure it has O(n*m) since - in the worst case - it always

    Me too. BM's worst case IS O(n*m). KMP's worst case is optimal.

    BM's average case is much better, which makes it worth taking the
    risk of hitting a worst case (the user has only themself to blame
    :).

> Angela Schmidt   Internet: S_ASchmidt@iravcl.ira.uka.de  |        //
--
*** John Bickers, TAP, NZAmigaUG.        jbickers@templar.actrix.gen.nz ***
***         "Endless variations, make it all seem new" - Devo.          ***