boyer-moore-horspool

KO | EN

gitlite — search

#typescript #ai-agents #ai #dsh-plugin #deepseek-harness #open-source #claude-code #codex #cli #developer-tools #react #windows

boyer-moore-horspool

★ 117 Open GitHub ↗

Booyer-Moore-Horspool string search algorithm implementation in C++

// repository documentation

Was this content helpful?

★ 0 (0 ratings)

Introduction
============
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: http://blog.phusion.nl/2010/12/06/efficient-substring-searching/

Files
-----

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

### BoyerMooreAndTurbo.cpp
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.

### StreamBoyerMooreHorspool.h
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.cpp
Benchmark program. Used in combination with the `run_benchmark` Rake task.

### TestMain.cpp
Unit test runner program.

Testing and benchmarking
------------------------

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

rake test
    ./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.

boyer-moore-horspool

Explore Similar Repositories

Was this content helpful?

Recent Feedback

Download README