Booyer-Moore-Horspool string search algorithm implementation in C++
HTML C++ Ruby
Latest commit 10e25ed Oct 10, 2016 @FooBarWidget committed on GitHub Merge pull request #1 from ZaMaZaN4iK/master
[fix] Fixed missed <climits> in Horspool.cpp
Failed to load latest commit information.
.gitignore Autogenerate benchmark input files. Dec 4, 2010
Horspool.cpp [fix] Fixed missed <climits> Oct 10, 2016
HorspoolTest.cpp Add yet more tests. Dec 4, 2010 Fix README Dec 28, 2011
StreamBoyerMooreHorspool.h Fix comments Dec 28, 2011
StreamTest.cpp Add another test, just to be sure Dec 28, 2011
tut_reporter.h Import some build and test files. Dec 3, 2010


This repository contains various C++ implementations of the Boyer-Moore string search algorithm and derivative algorithms. These family of algorithms allow fast searching of substrings, much faster than strstr() and memmem(). The longer the substring, the faster the algorithms work. The implementations are written to be both efficient and minimalist so that you can easily incorporate them in your own code.

This blog post has more information:



Implements Boyer-Moore-Horspool. HorspoolTest.cpp is the unit test file.


Implements Boyer-Moore and Turbo Boyer-Moore. No special test files, but they're used in the benchmark program which serves as a basic sanity test.


A special Boyer-Moore-Horspool implementation that supports "streaming" input. Instead of supplying the entire haystack at once, you can supply the haystack piece-by-piece. This makes it especially suitable for parsing data that you may receive over the network. This implementation also contains various memory and CPU optimizations, allowing it to be slightly faster and to use less memory than Horspool.cpp. See the file for detailed documentation.

Unit tests are in StreamTest.cpp.


Benchmark program. Used in combination with the run_benchmark Rake task.


Unit test runner program.

Testing and benchmarking

You need Ruby and Rake. To compile the unit tests:

rake test

To run the benchmarks:

rake run_benchmark

Which algorithm to use?

I've found that, on average, Boyer-Moore-Horspool performs best thanks to its simple inner loop which can be heavily optimized. It has pretty bad worst-case performance but the worst case (or even bad cases) almost never occur in practice.