Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!zaphod.mps.ohio-state.edu!unix.cis.pitt.edu!dsinc!bagate!cbmvax!cbmehq!cbmdeo!lenler!moria!bojsen
From: bojsen@moria.uucp (Per Bojsen)
Newsgroups: comp.sys.amiga.programmer
Subject: Re: The Boyer-Moore string searching algorithm
Message-ID: <194e56da.ARN3789@moria.uucp>
Date: 15 Jun 91 21:34:02 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> <4418.tnews@templar.actrix.gen.nz>
        <1991Jun13.104318.24450@ira.uka.de>
Reply-To: cbmehq!moria!bojsen
Followup-To: comp.sys.amiga.programmer
Organization: IDUN-Soft Aps.
Lines: 34

In article <1991Jun13.104318.24450@ira.uka.de>, |S| Angela Schmidt writes:

> In <4418.tnews@templar.actrix.gen.nz> jbickers@templar.actrix.gen.nz writes:
>
> >     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
> >     :).
> >
>
> Sorry, John, we were both wrong... :-(
>
Yes.  Please disregard my rebuttal to your previous post!

> I've looked into another book and I have to excuse me. Boyer&Moore only
> needs linear time in the worst case.
> Some books seem to simplify the algorythm. Let me descripe the difference
> to the real algorythm.
>
The simple algorithm seems to be Horspools simplified BM.

> A propos: In normal case the simple algorythm is not slower than the real one.
> but it is much easyer to implementate... ;-)
>
Well, the real BM wasn't that difficult to implement either!

--
.------------------------------------------------------------------------------.
|  Greetings from Per Bojsen.                                                  |
+------------------------------+-----------------------------------------------+
|  EMail: cbmehq!lenler!bojsen | "Names do have power, after all, that of      |
|     Or: bojsen@dc.dth.dk     |  conjuring images of places we have not seen" |
`------------------------------+-----------------------------------------------'