Re: gnulib's Knuth-Morris-Pratt implementation (was: memmem issues)

[Eric Blake]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

According to James Youngman on 12/20/2007 3:59 AM:
> I've been fiddling around with Bruno's KMP code recently.  I like it a
> lot.   I wish though there was some way for the caller to indicate
> that they are willing to amortise the cost of the KMP initialisation
> over many calls (that is, that we will look for this needle in many
> haystacks).

Also, I wonder if Boyer-Moore would be any more effective than KMP in the
average case (both have worst-case linear complexity, but we know that in
general, we aren't always dealing with worst-case).

http://en.wikipedia.org/wiki/Knuth-morris-pratt
http://en.wikipedia.org/wiki/Boyer-Moore_string_search_algorithm

- --
Don't work too hard, make some time for fun as well!

Eric Blake             address@hidden
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.5 (Cygwin)
Comment: Public key at home.comcast.net/~ericblake/eblake.gpg
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFHam2z84KuGfSFAYARAvj3AKCS6WansG2OLZexRuWR8nA6BanZ7QCfWcOs
hefSalc6XYNQSMlEqhzFDcc=
=9Sie
-----END PGP SIGNATURE-----