Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!sdd.hp.com!caen!sol.ctr.columbia.edu!ira.uka.de!news From: S_ASCHMIDT@iravcl.ira.uka.de (|S| Angela Schmidt) Newsgroups: comp.sys.amiga.programmer Subject: Re: The Boyer-Moore string searching algorithm Message-ID: <1991Jun13.104318.24450@ira.uka.de> Date: 13 Jun 91 11:17:11 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> Sender: news@ira.uka.de (USENET News System) Organization: University of Karlsruhe, FRG (Informatik Rechnerabteilung) Lines: 60 In-Reply-To: jbickers@templar.actrix.gen.nz's message of 13 Jun 91 08: 02:48 GMT X-News-Reader: VMS NEWS 1.08 In <4418.tnews@templar.actrix.gen.nz> jbickers@templar.actrix.gen.nz 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. 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. *** Sorry, John, we were both wrong... :-( 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. If the character you test does not appear in the string, both algorythms do the same thing: They skip m characters. And if it does appear in the string, both begin to test, if it's the string we search. If it's not the searched string, the real Boyer&Moore does something, that causes the linear time: It does not skip one character to the right as the simple algorythm does, it skips several characters - depending on the position where the mismatch appeared. This behavior is like that of the KMP-algorythm. So the real Boyer&Moore needs the same time as KMP in worst case. But in the normal case it is - of course - much better. A propos: In normal case the simple algorythm is not slower than the real one. but it is much easyer to implementate... ;-) Bye Angela ---------------------------------------------------------+--------------------- Angela Schmidt Internet: S_ASchmidt@iravcl.ira.uka.de | // (Nessy in IRC) BITNET: UK8B@DKAUNI2.BITNET | Amiga // Phone: +49 731 712316 & 721 6904-263 | \\ // only 1000 MEZ: (10am-9pm) (12pm-10pm) | \X/ the real one! ---------------------------------------------------------+--------------------- ---------------------------------------------------------+--------------------- Angela Schmidt Internet: S_ASchmidt@iravcl.ira.uka.de | // (Nessy in IRC) BITNET: UK8B@DKAUNI2.BITNET | Amiga // Phone: +49 731 712316 & 721 6904-263 | \\ // only 1000 MEZ: (10am-9pm) (12pm-10pm) | \X/ the real one! ---------------------------------------------------------+---------------------