Introduction

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)O(n/m) comparisons on average (n = text length, m = pattern length), and O(n+m)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)O(n) in the worst case on a general alphabet — Boyer-Moore effectively achieves that bound.

Try It

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>Pattern <input id="pat" value="EXAMPLE" maxlength="16" spellcheck="false"/></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">Reset</button>
    <button id="stepBtn" type="button">Step</button>
    <button id="runBtn" type="button">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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Boyer-Moore string search — bad-character + good-suffix rules.
// Preprocessing O(m + |Σ|); search O(n/m) average, O(n+m) worst case.
// Finds ALL (possibly overlapping) occurrences.

function buildBadChar(pat) {
  const bc = {};
  for (let i = 0; i < pat.length; i++) bc[pat[i]] = i;
  return bc;
}

// Standard good-suffix table (suffix[] auxiliary array method).
// gs[j] = shift amount when mismatch occurs at pattern position j (0-indexed from left).
function buildGoodSuffix(pat) {
  const m = pat.length;
  const suffix = new Array(m).fill(0);
  suffix[m - 1] = m;
  let g = m - 1, f = 0;
  for (let i = m - 2; i >= 0; i--) {
    if (i > g && suffix[i + m - 1 - f] < i - g) {
      suffix[i] = suffix[i + m - 1 - f];
    } else {
      if (i < g) g = i;
      f = i;
      while (g >= 0 && pat[g] === pat[g + m - 1 - f]) g--;
      suffix[i] = f - g;
    }
  }

  const gs = new Array(m).fill(m);

  // Case 1: border (prefix = suffix) shift
  let j = 0;
  for (let i = m - 1; i >= -1; i--) {
    if (i === -1 || suffix[i] === i + 1) {
      for (; j < m - 1 - i; j++) {
        if (gs[j] === m) gs[j] = m - 1 - i;
      }
    }
  }

  // Case 2: matched suffix appears elsewhere in pattern
  for (let i = 0; i <= m - 2; i++) {
    gs[m - 1 - suffix[i]] = m - 1 - i;
  }

  return gs;
}

// --- State ---
let text, pat, bc, gs, offset, cmpJ, matches, done;

function init() {
  pat  = (document.getElementById('pat').value || '').toUpperCase().replace(/[^A-Z0-9 ]/g, '');
  text = (document.getElementById('txt').value || '').toUpperCase().replace(/[^A-Z0-9 ]/g, '');
  if (!pat || !text) { setStatus('Enter a pattern and text.', ''); return; }
  bc = buildBadChar(pat);
  gs = buildGoodSuffix(pat);
  offset = 0;
  cmpJ = pat.length - 1; // compare from right end
  matches = [];
  done = false;
  clearLog();
  setStatus('Ready — press Step or Run all.', '');
  render(null, null);
}

function step() {
  if (done) { setStatus('Search complete.', ''); return; }
  if (!pat || !text) return;

  const m = pat.length;
  const n = text.length;

  if (offset + m > n) {
    done = true;
    const msg = matches.length
      ? fmt(matches.length > 1 ? '✓ Found %n% matches at positions %pos%.' : '✓ Found %n% match at position %pos%.', { n: matches.length, pos: matches.join(', ') })
      : '✗ Pattern not found in text.';
    setStatus(msg, matches.length ? 'ok' : 'bad');
    render(null, null);
    return;
  }

  const ti = offset + cmpJ;
  const tc = text[ti];
  const pc = pat[cmpJ];
  render(ti, cmpJ);

  if (tc === pc) {
    if (cmpJ === 0) {
      matches.push(offset);
      addLog(fmt('offset=%offset% ✓ Full match at position %offset%! Shift by gs[0]=%v%', { offset: offset, v: gs[0] }));
      setStatus(fmt('✓ Match found at position %offset%!', { offset: offset }), 'ok');
      offset += gs[0];
      cmpJ = m - 1;
    } else {
      addLog(fmt('offset=%offset% j=%cmpJ% text[%ti%]=%tc%=pat[%cmpJ%] ✓ continue', { offset: offset, cmpJ: cmpJ, ti: ti, tc: tc }));
      setStatus('Characters match — scanning right-to-left…', '');
      cmpJ--;
    }
  } else {
    const bcShift = bc[tc] !== undefined ? cmpJ - bc[tc] : cmpJ + 1;
    const gsShift = gs[cmpJ];
    const shift = Math.max(1, Math.max(bcShift, gsShift));
    addLog(fmt('offset=%offset% j=%cmpJ% text[%ti%]=%tc% ≠ pat[%cmpJ%]=%pc% bad-char=%bcShift% good-suffix=%gsShift% → shift %shift%', { offset: offset, cmpJ: cmpJ, ti: ti, tc: tc, pc: pc, bcShift: bcShift, gsShift: gsShift, shift: shift }));
    setStatus(fmt(shift > 1 ? 'Mismatch: skip %shift% positions (bad-char %bcShift%, good-suffix %gsShift%)' : 'Mismatch: skip %shift% position (bad-char %bcShift%, good-suffix %gsShift%)', { shift: shift, bcShift: bcShift, gsShift: gsShift }), '');
    offset += shift;
    cmpJ = m - 1;
  }
}

function runAll() {
  for (let i = 0; i < 1000 && !done; i++) step();
  if (!done) { done = true; setStatus('Stopped (too many steps).', 'bad'); }
}

function render(activeTi, activePi) {
  const m = pat.length, n = text.length;

  const textRow = document.getElementById('textRow');
  textRow.innerHTML = '';
  for (let i = 0; i < n; i++) {
    const d = document.createElement('div');
    const isMatch = matches.some(o => i >= o && i < o + m);
    const isCmp   = (i === activeTi);
    d.className = 'ch ' + (isCmp ? 'text-cmp' : isMatch ? 'text-match' : 'text-bg');
    d.textContent = text[i];
    textRow.appendChild(d);
  }

  const patRow = document.getElementById('patRow');
  patRow.innerHTML = '';
  for (let i = 0; i < Math.min(offset, n); i++) {
    const g = document.createElement('div');
    g.className = 'ch gap';
    patRow.appendChild(g);
  }
  for (let j = 0; j < m; j++) {
    const d = document.createElement('div');
    // Chars to the RIGHT of cmpJ have already been compared and matched in this window
    const isMatched = (activePi !== null && j > activePi && !done);
    const isCmp = (j === activePi);
    d.className = 'ch ' + (isCmp ? 'pat-cmp' : isMatched ? 'pat-match' : 'pat-norm');
    d.textContent = pat[j];
    patRow.appendChild(d);
  }
}

function setStatus(t, cls) {
  const s = document.getElementById('status');
  s.textContent = t;
  s.className = 'status ' + cls;
}
function addLog(t) {
  const l = document.getElementById('log');
  const d = document.createElement('div');
  d.textContent = t;
  l.appendChild(d);
  l.scrollTop = l.scrollHeight;
}
function clearLog() { document.getElementById('log').innerHTML = ''; }

document.getElementById('resetBtn').addEventListener('click', init);
document.getElementById('stepBtn').addEventListener('click', step);
document.getElementById('runBtn').addEventListener('click', runAll);
document.getElementById('pat').addEventListener('input', init);
document.getElementById('txt').addEventListener('input', init);

init();
Result
Console

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.

The Real Complexity

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 cc, shift the pattern right so the rightmost occurrence of cc in the pattern lines up with the mismatch. If cc 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:

Scenario Comparisons
Best case (pattern not in alphabet) O(n/m)O(n/m)
Average case (random text) O(n/m)O(n/m)
Worst case (e.g. aaaa in aaaa...) O(n+m)O(n + m)
Preprocessing O(m + |Σ|)

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)O(n).

Status: solved. Boyer-Moore's complexity is fully characterized. Cole (1994) proved the O(n+m)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.

Where It Matters

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.

Conclusion

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)O(n + m), average-case O(n/m)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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/boyer-moore/Content licensed under CC BY-NC 4.0.