Sample Video Frame

Created by Zed A. Shaw Updated 2024-02-17 04:54:36

Exercise 39: String Algorithms

In this exercise, I'm going to show you a supposedly faster string search algorithm, and compare it to the one that exists in bstrlib.c called binstr. 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 of this algorithm is that it calculates a skip characters list as a first operation, then it uses this list to quickly scan through the string. It's supposed to be faster than brute force, so let's get the code into the right files and see.

First, I have the header:

Previous Lesson Next Lesson

Register for Learn C the Hard Way

Register today for the course and get the all currently available videos and lessons, plus all future modules for no extra charge.