strstr sources: a summary of responses

[Brad Appleton]

In article <26215 at mimsy.umd.edu> chris at mimsy.umd.edu (Chris Torek) writes:
>In article <1158 at umvlsi.ecs.umass.edu> srivasta at 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 at travis.ssd.csd.harris.com   Harris Computer Systems
                          ...!uunet!hcx1!brad          Fort Lauderdale, FL USA
~~~~~~~~~~~~~~~~~~~~ Disclaimer: I said it, not my company! ~~~~~~~~~~~~~~~~~~~