Boyer–Moore

In August 2010 the FreeBSD mailing list was arguing about why BSD grep was slower than GNU grep. Mike Haertel, the original author of GNU grep, joined in and explained the main trick in capital letters: “GNU grep is fast because it AVOIDS LOOKING AT EVERY INPUT BYTE.” It searches with the Boyer–Moore algorithm: it looks first at the last letter of the pattern and decides from a table how far it can jump ahead. Below, this algorithm looks for a name or a phrase in Part One of “War and Peace” in the Russian original. The dots above the letters mark the ones it looked at at all.

«Князь Андрей» (“Prince Andrei”) occurs 57 times in Part One. The naive search, which places the pattern at every position, made 252,256 comparisons, more than there are characters in the text. Boyer–Moore made 27,550: one comparison per nine characters. Six jumps in ten were the full length of the pattern, twelve characters: under the last cell of the window was a letter that does not occur in «князь Андрей» at all. Switch to the thirty-character phrase «Ну, здравствуйте, здравствуйте» (“Well, hello, hello”): 12,784 comparisons, one per nineteen characters. On the four-letter «Пьер» (“Pierre”) the gain is more modest, 3.6 times. Look at the strip at the bottom too, which is all of Part One: the grey bars show how many comparisons per letter the naive search makes, the coloured ones the chosen algorithm. The naive bars reach the dashed line “one comparison per letter”, at least one for each letter, while Boyer–Moore's are several times lower, and the longer the pattern, the lower they are.

The idea

Place the pattern against the text, but compare from the right end of the window. If the text letter under the last cell does not occur in the pattern at all, no window covering that letter can match, and the pattern jumps over it entirely, m positions at once. If it does occur, shift the pattern so that its nearest copy of that letter comes under it. Comparing from right to left gives more knowledge about the text before the first mismatch, and tables built in advance from the pattern alone turn that knowledge into long jumps.

The naive search moves the pattern by one position whatever happens. Boyer and Moore noticed that after a mismatch a lot is known about the text, and the shift can be computed. The longer the pattern, the farther the jump: a long pattern is found faster than a short one. This is the main thing that sets the algorithm apart from KMP, which reads every letter of the text exactly once.

Two shift rules

Suppose the window was compared from right to left, the last letters matched, and at position j of the pattern the text letter c did not match p[j]. The algorithm computes two shifts and takes the larger.

The bad character rule: shift the pattern so that the rightmost copy of the letter c in the pattern comes under it (the last cell does not count). If c is not in the pattern, the pattern jumps over it entirely. If the rightmost copy stands to the right of the mismatch, the rule suggests a backward shift and is useless; then the second rule decides. The table for this rule, the last occurrence of each letter of the alphabet in the pattern, is built in O(m + σ), where σ is the size of the alphabet.

The good suffix rule: the matched end u of the pattern is what we know for certain about the text. Shift the pattern to the nearest copy of u within the pattern that is preceded by a letter other than p[j]: the same letter before the copy would give the same mismatch. If there is no such copy, shift so that the longest beginning of the pattern matches the tail of u.

Below is the example from Boyer and Moore's 1977 paper: the pattern AT-THAT in the string WHICH-FINALLY-HALTS.--AT-THAT-POINT. At each mismatch the scene draws both candidates: in orange, which letter of the pattern the bad character rule puts under the text letter; in blue, where the good suffix rule finds a copy of the matched end.

The first three windows are decided by the bad character. Under the last cell of the first window is F, which is not in the pattern: a jump of the full length, 7. In the second window it is “-”, which stands in the pattern four letters from the end: a shift of 4. In the third, T matched, and L is not in the pattern, so the pattern jumps over it: a shift of 6. In the fourth window “AT” matched, and before it the text has “-” instead of H. The bad character would give only 2: the nearest “-” in the pattern is right there. The good suffix gives 5: “AT” stands at the beginning of the pattern, and the pattern is placed so that the beginning lies on the matched “AT”. The fifth window is an occurrence. 15 comparisons in all, against 40 for the naive search on the same string.

Switch to DNA. In an alphabet of four letters almost any text letter is in the pattern, and the bad character gives short shifts: 1 and 4. In the last window a single G matched, and before it the text has C: the bad character would give 5, the good suffix gives 7, since the other G's in the pattern come after the same A that failed to match, and only the G at the very beginning of the pattern will do. And on “aaaa…” every window is an occurrence, the shift is always 1, and the algorithm compares each window in full: 52 comparisons. Tick “Galil's rule” and there will be 16; more on it below.

Horspool: one table

In 1980 Nigel Horspool proposed a simplification that became the workhorse. There is no good suffix. The bad character is always the same one, the text letter under the last cell of the window, wherever the mismatch happened. The window shifts so that the rightmost copy of this letter among the first m − 1 letters of the pattern comes under it; if there is no copy, by m. One table, a shift that is always positive, a dozen lines of code.

On prose Horspool is hardly worse than the full algorithm. In Part One of the novel both make the same number of comparisons for «Пьер» and «князь Андрей», and for the thirty-character phrase the difference is under 5 %. The good suffix kicks in only when a long end of the pattern has matched, while in prose the very first letter from the right usually does not match. On DNA the picture is different: on a 32-letter pattern Horspool makes 28,123 comparisons per 100,000 letters, the full Boyer–Moore 15,675.

Why the shifts miss nothing

The good suffix table is conveniently built with the Z-function. You need to know how long the common end of each beginning of the pattern and the whole pattern is, and this is the Z-function of the reversed pattern read backwards. This is how Dan Gusfield derives it in a book, and how it is built in the listing below.

Code

The bad character table is a dictionary “letter → shift” in Python and a map in Go; letters not in the pattern get the shift m. Both search functions also count comparisons, and at the end come the 1977 example step by step and a table on random texts.

The last table of the output is a short reference on the algorithm's behaviour. On a random text of 26 letters an eight-letter pattern is found with 14,899 comparisons per 100,000 letters, a 32-letter one with 5148: a longer pattern means a faster search. On random DNA with the same lengths, 47,859 and 15,675. And two lines about a text of nothing but “a”, more on which below.

Now on a real text. The program looks for five patterns in Part One of the novel, first by letters and then, in the last column, by UTF-8 bytes, the way grep searches:

By bytes it comes out worse. «Пьер» by letters takes 67,545 comparisons, by bytes 77,197. In UTF-8 every Cyrillic letter is two bytes, and the first of them is almost the same for all lowercase and capital letters: D0 or D1. The pattern in bytes is twice as long, but under the last cell of the window there is often a byte that occurs in the pattern many times, and the jumps are shorter.

What it costs

Preparation is O(m + σ): the bad character table over the whole alphabet and the good suffix table in O(m). Memory is the same. Beyond that everything depends on the text.

On average, less than one comparison per letter. If the alphabet is large and the pattern rarely occurs in the text, the letter under the last cell of the window most often is not in the pattern or stands far from its end, and the window jumps almost m. There are then on the order of n/m windows, usually with one or two comparisons each. This is what is called sublinearity: the time is less than the length of the text, and the less the longer the pattern. Compare four texts, Russian prose by letters and by bytes, English prose, and DNA:

With a 16-character pattern Horspool makes 0.1 comparisons per letter on Russian prose, 0.11 on English, 0.15 on the same Russian letters in bytes. On DNA 0.34, and from there the line hardly goes down: in a four-letter alphabet the last letter of the window almost always stands somewhere near the end of the pattern, and the jumps are short however long the pattern. Switch to the full Boyer–Moore: the good suffix pulls DNA down to 0.2 with a 64-letter pattern. The naive search makes slightly more than one comparison per character on all four texts.

Time on the same Part One of the novel: the naive search, Horspool and the language's built-in search, the pattern being a piece of the text itself of length m.

The naive search takes the same time at any pattern length, while Horspool speeds up almost twofold with every doubling of the pattern: in Python, from a 2-character pattern to a 64-character one, the time fell 21 times. With two characters Horspool is slower than the naive search: the jumps are short, and every window costs an extra table lookup. Python's built-in search is faster than both: it is written in C and is itself a mix of Boyer–Moore and Horspool. Go's built-in search, on the contrary, loses to Horspool on long patterns; why is told in the article on the naive search.

The worst case. Horspool, on a text of nothing but “a” with the pattern “b” and seven “a”, compares all eight letters in each window, trips over the “b” and shifts by one position: there is an “a” under the last cell again. In the listing's output that is 799,944 comparisons per 100,000 letters, eight times more than the naive search, which starts comparing with the “b”. The full Boyer–Moore is linear here: the good suffix sees that “aaaaaaa” before a “b” occurs nowhere else in the pattern and jumps by 8.

But the full algorithm has a weak spot too: many occurrences. A pattern of eight “a” in a text of nothing but “a” occurs at almost every position. After an occurrence the pattern shifts by its period, one letter, and the next window is compared in full again: 799,944 comparisons once more. In 1979 Zvi Galil proposed remembering that after a shift by the period the first m − period letters of the window have already matched, and not comparing them again. With Galil's rule there are exactly 100,000 comparisons, one per letter.

What grep and memmem really run

The textbook version with two tables works almost nowhere in pure form. Programs run its descendants, each tuned to the processor.

GNU grep. In version 3.12 (2025) a single fixed string is found by the file src/kwset.c, which Mike Haertel wrote in August 1989. A comment in the code says it plainly: Boyer–Moore if there is one pattern, Aho–Corasick if there are several. The bad character table looks, as in Horspool, at the last byte of the window, and the jump loop is unrolled: the window jumps several times in a row until the last byte of the pattern is under the last cell. When the jumps come out short, grep switches to searching for that byte with functions like memchr, which check a whole machine word at once. Once the last bytes match, the good suffix table comes into play. For a regular expression grep extracts strings that must occur in any match and searches for them first with the same code, and a simple pattern without special characters is switched straight to -F mode. The grep documentation says so: where possible, Boyer–Moore is used for one fixed string and Aho–Corasick for several.

glibc. In the C standard library for Linux, version 2.44 (2026), memmem and strstr work like this. Patterns of one or two bytes (up to three in strstr) are found by a separate simple loop. Patterns up to 256 bytes use a “new modified Horspool algorithm”, as the source calls it: the shift table is built not from one letter but from a pair of neighbouring bytes, folded by a hash into a cell number, and the main loop stops only when the pair of bytes at the end of the window matches the end of the pattern by hash. The 256-byte limit keeps each shift in one byte and the table in 256 bytes, and also guarantees linear time. Longer patterns are found by the Crochemore–Perrin two-way algorithm. This Horspool variant was written in 2019 by Wilco Dijkstra. On x86-64 strstr first tries its own SSE2 vector version, which in some cases hands the work to this generic function.

Other languages. Python's str.find uses, in the words of its source, a mix of Boyer–Moore and Horspool for short patterns and the same two-way algorithm for long ones; details are in the article on the naive search. In C++, from C++17 on, std::search can be given std::boyer_moore_searcher or std::boyer_moore_horspool_searcher. In Go strings.Index does not use Boyer–Moore, but the strings package has it inside: strings.NewReplacer uses it when there is one old string longer than one byte.

Where it is weaker

• A small alphabet. On DNA almost every text letter is in the pattern, and the bad character gives short shifts. For DNA and binary data, algorithms that look at several letters at once, like glibc on pairs of bytes, or at whole machine words, are a better fit.
• Short patterns. With m = 2–3 there is almost nowhere to jump, and a simple loop with a vectorised check of the first letter wins; this is what libraries do.
• A stream. Boyer–Moore needs a whole window of text, while in a stream, where letters arrive one at a time and there is no way back, KMP works.
• Patterns with “any letter”. The tables derive equality of some letters from equality of others, and wildcards break them. Here the naive search or an automaton is simpler.

History

Robert Boyer and J Strother Moore, as Moore recalled, came up with the algorithm around 1975. The paper “A fast string searching algorithm” appeared in Communications of the ACM in October 1977. In the same year Knuth, Morris and Pratt, in their paper on KMP, also analysed the Boyer–Moore algorithm and proved it linear when the pattern does not occur in the text. In 1979 Zvi Galil made the algorithm linear always, in 1980 Nigel Horspool simplified it to one table, and in 1991 Richard Cole found the tight bound on the number of comparisons. The Boyer–Moore file in GNU grep was written in 1989; it has been rewritten many times since, but the idea has stayed the same: do not look at every byte.

Problems

In the first problem you count honestly how much work Horspool does on real texts, without getting the table wrong. In the second you build the good suffix table for a pattern of a hundred thousand characters in linear time.