I was trying to remember the name of the cool pattern matching technique that takes less than linear time. I thought it was by Knuth but his version is the simple, obvious way.
Boyer-Moore is genius - it works through the text by making big jumps based on the content of the search string.
I found this cool animation (which just happens to be from my alma mater, UCI). Test it once with the Knuth-Morris-Pratt version and then again with Boyer-Moore.
© 2005-2008 Stephen Clarke-Willson, Ph.D. - All Rights Reserved.