Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!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: <194e51f5.ARN3784@moria.uucp>
Date: 15 Jun 91 21:13:09 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>
Reply-To: cbmehq!moria!bojsen
Followup-To: comp.sys.amiga.programmer
Organization: IDUN-Soft Aps.
Lines: 31

In article <4418.tnews@templar.actrix.gen.nz>, John Bickers writes:

> 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 [Knuth-Morris-
      Pratt]
>
> > Sorry, but I'm *very* shure it has O(n*m) since - in the worst case -
>
>     Me too. BM's worst case IS O(n*m). KMP's worst case is optimal.
>
Nope!  BM *is* O(m+n) in the worst case.  Are you sure we are talking about
the same algorithm?  I'm talking about the Boyer-Moore algorithm that is
described in the paper by A.V. Aho in ``Algorithms and Complexity'', Volume A
of ``Handbook of Theoretical Computer Science''.  The algorithm was first
published by R.S. Boyer and J.S. Moore in ``A Fast String Searching Algorithm'',
Comm. ACM 20(10) (1977) pp 62--72.  Citing from Aho:

    ``3.8 Theorem.  The Boyer-Moore algorithm solves [the string searching
      problem] in O(m+n) time and O(m) space.''

I think you're talking about Horspool's simplification of the Boyer-Moore
algorithm.  Could that be it?

--
.------------------------------------------------------------------------------.
|  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" |
`------------------------------+-----------------------------------------------'