Boyer-Moore Search

Every time you press Ctrl+F or ask a database to LIKE '%pattern%', somewhere a program is hunting for a short string inside a very long one. The obvious approach — slide the pattern one position at a time and compare — works, but it reads every character of the text. On a 100 MB file that is a lot of reading.

In 1977 Robert S. Boyer and J Strother Moore published an algorithm that does something surprising: it reads the pattern from right to left, and whenever a character mismatches it consults two precomputed tables to jump forward by as many positions as possible — often skipping entire chunks of text without reading them.

The result is a search that can run faster than the length of the text itself — sublinear in the best and average case on natural language. That is not a typo: for long patterns in typical text, Boyer-Moore looks at fewer characters than there are characters in the file.

The algorithm is solved in the sense that its worst-case complexity is proven: $O(n/m)$ comparisons on average (n = text length, m = pattern length), and $O(n + m)$ in the worst case, established by Knuth, Morris and Pratt's complementary analysis and later refined by Cole (1994). No string-search algorithm can asymptotically beat $O(n)$ in the worst case on a general alphabet — Boyer-Moore effectively achieves that bound.

Type a pattern and a text below, then click Step to watch Boyer-Moore work one comparison at a time. The highlighted cell is the current comparison; arrows show the skip jump when a mismatch triggers a rule.

<div class="controls">
  <label>{{label_pattern}} <input id="pat" value="EXAMPLE" maxlength="16" spellcheck="false"/></label>
  <label>{{label_text}} <input id="txt" value="HERE IS A SIMPLE EXAMPLE OF THE TEXT" maxlength="60" spellcheck="false"/></label>
  <div class="btns">
    <button id="resetBtn" type="button">{{btn_reset}}</button>
    <button id="stepBtn" type="button">{{btn_step}}</button>
    <button id="runBtn" type="button">{{btn_run_all}}</button>
  </div>
</div>
<div class="vis-wrap">
  <div id="textRow" class="char-row"></div>
  <div id="patRow" class="char-row pat-row"></div>
</div>
<div id="status" class="status"></div>
<div id="log" class="log"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 14px; }
.controls { display: flex; flex-direction: column; gap: .5rem; margin-bottom: .7rem; }
.controls label { display: flex; align-items: center; gap: .4rem; font-weight: 600; font-size: .85rem; }
.controls input { font: 600 15px ui-monospace, monospace; padding: .3rem .5rem; border: 1px solid #adb1b8; border-radius: 6px; flex: 1; text-transform: uppercase; }
.btns { display: flex; gap: .4rem; }
button { font: 600 13px system-ui, sans-serif; padding: .35rem .75rem; border: 1px solid #1d3557; background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; }
button#resetBtn { background: #fff; color: #1d3557; }
.vis-wrap { overflow-x: auto; padding-bottom: .3rem; min-height: 80px; }
.char-row { display: flex; gap: 2px; min-width: max-content; }
.pat-row { margin-top: 2px; }
.ch { width: 26px; height: 28px; display: flex; align-items: center; justify-content: center;
      font: 700 14px ui-monospace, monospace; border-radius: 5px; border: 1px solid transparent; }
.ch.text-bg { background: #e8eef3; color: #1d3557; border-color: #cdd9e3; }
.ch.text-match { background: #0a7d33; color: #fff; border-color: #086629; }
.ch.text-cmp   { background: #1d3557; color: #fff; border-color: #16294a; }
.ch.pat-norm   { background: #f0f4f8; color: #333; border-color: #b0bcc8; }
.ch.pat-cmp    { background: #e63946; color: #fff; border-color: #c92f3c; }
.ch.pat-match  { background: #0a7d33; color: #fff; border-color: #086629; }
.ch.gap        { background: transparent; border-color: transparent; }
.status { font-size: .95rem; font-weight: 600; margin: .5rem 0 .3rem; min-height: 1.3em; color: #1d3557; }
.status.ok  { color: #0a7d33; }
.status.bad { color: #e63946; }
.log { font-size: .8rem; color: #555; max-height: 90px; overflow-y: auto; line-height: 1.5; }
.log div { border-bottom: 1px solid #eee; padding: 1px 0; }

// Code not found

Notice what happens on a mismatch: instead of sliding one position, Boyer-Moore consults the bad-character table (how far right is this mismatch character in the pattern?) and the good-suffix table (if the right end matched, how far do we slide to realign?) and takes the larger skip. On repeated characters like spaces or 'e' in English prose, the jumps are huge — the algorithm genuinely reads only a fraction of the text. Related: see pattern matching for a comparison with KMP and Rabin-Karp.

Boyer-Moore uses two precomputed shift tables, built in O(m + |Σ|) time where m is the pattern length and |Σ| is the alphabet size.

Bad-character rule: when the character at the mismatch position in the text is $c$, shift the pattern right so the rightmost occurrence of $c$ in the pattern lines up with the mismatch. If $c$ doesn't appear in the pattern at all, shift the entire pattern past the mismatch. This alone can skip m positions in one step.

Good-suffix rule: if a suffix of the pattern matched before the mismatch, shift the pattern to the next occurrence of that suffix (or the longest prefix of the pattern that matches a suffix of what matched). This prevents missing any real occurrence.

The take-the-maximum of both shifts at each step is the final advance.

Complexity summary:

The key insight is that on a large alphabet and a long pattern, most text characters are never read at all. This is provably optimal up to constants — no comparison-based search can do better in the worst case than $O(n)$.

Status: solved. Boyer-Moore's complexity is fully characterized. Cole (1994) proved the $O(n + m)$ worst-case bound and showed that the original algorithm makes at most 3n character comparisons. The pattern matching landscape is complete for one-dimensional exact search.

Fast string search underlies an enormous range of software, and Boyer-Moore (or its descendants) shows up in all of them:

• Text editors and IDE search: most Ctrl+F implementations use Boyer-Moore-Horspool (a simplified variant) or Boyer-Moore itself for the common case where the pattern is long enough for skipping to pay off.
• grep and command-line tools: GNU grep uses Boyer-Moore as its primary inner loop, which is why it can search a gigabyte file in milliseconds.
• Intrusion detection systems (IDS): tools like Snort pattern-match thousands of signatures against network traffic in real time. Boyer-Moore variants make this feasible.
• Bioinformatics: searching for motifs or restriction sites in a genome means scanning gigabases. Boyer-Moore's sublinear average case translates directly into wall-clock speed.
• Antivirus scanning: signature-based engines scan files for known malware byte sequences — a workload that needs exactly the skip-heavy characteristics of Boyer-Moore.

The same right-to-left insight also inspired the Apostolico-Giancarlo algorithm and the Two-Way algorithm used in some C library memmem implementations, proving that the 1977 paper still echoes through modern systems code.

Boyer-Moore's central trick is beautifully counterintuitive: read the pattern backwards, and use mismatches as information about how far to leap forward. Two precomputed tables — bad character and good suffix — turn every mismatch into a potentially large jump, so the algorithm can race through text faster than a simple left-to-right reader.

The result is a solved problem in the best sense: worst-case $O(n + m)$, average-case $O(n/m)$, preprocessing O(m + |Σ|), and decades of practical refinement in grep, editors and genome tools. When someone types Ctrl+F and the answer appears before their finger leaves the key, Boyer-Moore is almost certainly doing the heavy lifting.

For related ideas, explore pattern matching — the broader landscape of exact and approximate string search.