[racket-dev] String search in mred/private/wxme: knuth-bendix?!

From: Matthew Flatt (mflatt at cs.utah.edu)
Date: Thu Nov 29 18:15:49 EST 2012

At Thu, 29 Nov 2012 15:22:17 -0700, Danny Yoo wrote:
> I'm staring at do-find-string-all's implementation, and right before the
> string-matching logic, there's a mysterious comment "Knuth Bendix" in
> there.  I'm staring at the code some more, and it looks more like KMP
> (Knuth-Morris-Pratt) to me.

Yes, I wrote the wrong algorithm name in the comment.

> Assuming that it is KMP, is there a reason why we're not using Boyer-Moore
> here instead?  My understanding was BM was faster than KMP for common
> situations.

KMP is just the algorithm I knew at the time.

Since `find-string' can find "editor:info-mixin searching%" at the end
of "collects/frameworks/private/text.rkt" in 15-20ms, I doubt that it
has been a bottleneck for, say, searching in DrRacket.


Posted on the dev mailing list.