O'Reilly logo

Learn C the Hard Way: A Clear & Direct Introduction To Modern C Programming by Zed A. Shaw

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Exercise 39. String Algorithms

In this exercise, I’m going to show you a supposedly faster string search algorithm, called binstr, and compare it to the one that exists in bstrlib.c. The documentation for binstr says that it uses a simple “brute force” string search to find the first instance. The one that I’ll implement will use the Boyer-Moore-Horspool (BMH) algorithm, which is supposed to be faster if you analyze the theoretical time. Assuming my implementation isn’t flawed, you’ll see that the practical time for BMH is much worse than the simple brute force of binstr.

The point of this exercise isn’t really to explain the algorithm, because it’s simple enough for you to read the “Boyer-Moore-Horspool algorithm” page on Wikipedia. The gist ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required