Path: utzoo!attcan!uunet!wuarchive!usc!zaphod.mps.ohio-state.edu!uakari.primate.wisc.edu!uflorida!travis!brad
From: brad@SSD.CSD.HARRIS.COM (Brad Appleton)
Newsgroups: comp.lang.c
Subject: Re: strstr sources: a summary of responses
Summary: Check out CACM Vol. 33 No. 8 pp. 132-142 (August 1990)
Keywords: ANSI lib, strstr
Message-ID: <800@travis.csd.harris.com>
Date: 27 Aug 90 15:17:08 GMT
References: <1158@umvlsi.ecs.umass.edu> <26215@mimsy.umd.edu>
Sender: news@travis.csd.harris.com
Organization: Harris Computers Systems Division, Fort Lauderdale,FL
Lines: 37

In article <26215@mimsy.umd.edu> chris@mimsy.umd.edu (Chris Torek) writes:
>In article <1158@umvlsi.ecs.umass.edu> srivasta@umvlsi.ecs.umass.edu
>(Manoj Srivastava) posts a Boyer-Moore based strstr() by John Lacey.
>
>>And finally, an implementation of the Boyer-Moore algorithm. I
>>am not sure offhand, but while the worst case complexity remains
>>O(N+M), the avg case behaviour is O(N/M) ???
>
>(where N is the length of the string being searched and M is the length
>of the substring, aka pattern).  Yes, it is N/M.

Interestingly enough ... This August's issue of Communications of The ACM
has an article on page 132 entitled "A Very Fast Substring Search Algorithm".

The abstract reads as follows:

	This article describes a substring search algorithm that is
	faster than the Boyer-Moore algorithm. This algorithm does 
	not depend on scanning the pattern string in any particular
	order. Three variations of the algorithm are given that use
	three different pattern scan orders. These include:
	   (1) a "Quick Search" algorithm;
	   (2) a "Maximal Shift" algorithm; and
	   (3) an "Optimal Mismatch" algorithm;

The article comes complete with an implementation in C!
I strongly encourage people to take a peek at it.

ANYWAY -- IMHO, unless you are going to be looking for the same
          string multiple times... it is not worth the effort
          to get fancy (a la Knuth-Morris-Pratt or Boyer-Moore)!
          I think most strstr() function use the classic
          "Brute-Force" approach.
______________________ "And miles to go before I sleep." ______________________
 Brad Appleton        brad@travis.ssd.csd.harris.com   Harris Computer Systems
                          ...!uunet!hcx1!brad          Fort Lauderdale, FL USA
~~~~~~~~~~~~~~~~~~~~ Disclaimer: I said it, not my company! ~~~~~~~~~~~~~~~~~~~