Date: Thu, 04 Oct 2001 09:07:19 -0700 From: Farooq Mela <fmela0@sm.socccd.cc.ca.us> To: "Andrew L. Neporada" <andrew@nas.dgap.mipt.ru> Cc: Bakul Shah <bakul@bitblocks.com>, freebsd-hackers@freebsd.org Subject: Re: current strstr(3) implementation is slow Message-ID: <3BBC8937.44A77CF9@sm.socccd.cc.ca.us> References: <Pine.BSF.4.21.0110020948250.33545-100000@nas.dgap.mipt.ru>
next in thread | previous in thread | raw e-mail | index | archive | help
"Andrew L. Neporada" wrote: > to Algorithms" book (AKA CLR) by MIT Press, more precisely "Knuth, Morris > and Pratt algorithm". Hmm, sounds good, much better than naive string matching algorithm. However I think it would be a good idea to check if the length of the pattern <= architecture's word size (i386 is 32, alpha is 64, etc), and if so use shift-or matching [Baeza-Yates & Gonnet, "A New Approach to Text Searching," CACM 35, Oct. 1992, 74-82]. Shift-or matching only requires an array of 256 * word size bits which can be on the stack, but KMP matching needs O(M) which must be malloc'ed. Shift-or is usually considerably faster than KMP algorithm, see paper for details. -- farooq <fmela0@sm.socccd.cc.ca.us> To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-hackers" in the body of the message
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?3BBC8937.44A77CF9>