↩ back to Exact Match

Boyer-Moore String Matching

KMP and naive search both compare a pattern against a text left to right, one character at a time, and neither ever looks at a text character before confirming everything to its left. Boyer-Moore compares right to left instead — check the pattern's last character against the text first — and that single reversal unlocks something left-to-right algorithms can't do: the very first comparison at a new alignment can already rule out large stretches of the text, before a single earlier character has been examined. Two independent rules turn a mismatch into a shift distance — the bad-character rule (where does the mismatching text character last occur in the pattern, if at all?) and the good-suffix rule (where else could the already-matched tail of the pattern plausibly realign?) — and the algorithm always takes whichever shift is larger, since neither rule can ever recommend skipping past a genuine match. On this page's own default example, searching "HERE IS A SIMPLE EXAMPLE" for "EXAMPLE", that combination finds the match in 15 character comparisons across 5 alignments — naive search needs 27 (checked below, not just claimed).

Try it

Enter a text and a pattern (up to 30 and 12 characters). Step through: both shift tables are built once, up front, from the pattern alone — no text involved yet — then each alignment compares right to left, and every mismatch (or full match) triggers a shift decision that shows both rules' proposed distance and which one won. The matched pattern lands in green; a mismatch flashes; the pattern's ghost cells show exactly how far each shift moved it.

Why it works

Comparing right to left means the very first character checked at a new alignment is the pattern's last one — so a mismatch there immediately says something about a text character further along than any left-to-right algorithm has looked at yet. That single piece of information is enough to compute a safe shift without re-examining anything to its left.

Bad-character rule: when text[s+j] mismatches pat[j], look up the last occurrence of that exact text character anywhere in the pattern. If it occurs at some earlier pattern position p < j, shifting right by j - p lines that occurrence up under the text character that just failed — the nearest place a match could plausibly start. If the character never occurs in the pattern at all, no alignment overlapping it can ever match, so the whole pattern shifts past it. A max(1, ...) floor keeps the shift moving forward even when the character reoccurs after position j in the pattern, which would otherwise compute a non-positive distance — see Pitfalls.

Good-suffix rule: after a mismatch at j, the characters pat[j+1..m-1] — the "good suffix" — are already known to match. Two cases, checked in order: case 1, that suffix recurs elsewhere in the pattern, not immediately preceded by the same character that just caused the mismatch (a recurrence that's actually informative, not coincidental) — shift to align that occurrence under the matched text. Case 2, no such interior recurrence exists, but some prefix of the pattern matches a suffix of the good suffix — shift so that prefix lines up, the closest thing left to a valid realignment. Neither case applying means shift the whole pattern past the matched region. This page's demo default hits case 1 at alignment 3: mismatching on 'I' against pattern index 2 leaves the good suffix "MPLE", which recurs nowhere else in "EXAMPLE" — so shift[3] falls through to case 2's prefix check, which also fails, landing on the full past-the-match shift of 6.

Why taking the larger of the two shifts is safe: each rule's shift is a proven lower bound on how far the pattern must move before another match could possibly start — bad-character from where the mismatching character last appears in the pattern, good-suffix from the matched suffix's own internal structure. Neither rule ever recommends a distance that could skip over a real match; a larger safe distance is still safe, so the max of two lower bounds is itself a valid lower bound. Concretely, on this page's default example: alignment 3's mismatch gives bad-character shift 3 (last 'I' isn't in the pattern) against good-suffix shift 6 — taking 6 skips three additional positions bad-character alone wouldn't have, and the demo's own comparison count above already accounts for it.

Reference implementation

This is the exact scheme the demo above steps through — bad-character table, good-suffix table (Gusfield's bpos/shift construction), then the combined search:

function lastOccurrenceTable(pat) {
  const table = {};
  for (let i = 0; i < pat.length; i++) table[pat[i]] = i;   // later index overwrites earlier — last wins
  return table;
}

function goodSuffixTable(pat) {
  const m = pat.length;
  const shift = new Array(m + 1).fill(0);
  const bpos = new Array(m + 1).fill(0);

  let i = m, j = m + 1;                 // case 1: interior recurrence of each suffix
  bpos[i] = j;
  while (i > 0) {
    while (j <= m && pat[i - 1] !== pat[j - 1]) {
      if (shift[j] === 0) shift[j] = j - i;
      j = bpos[j];
    }
    i--; j--;
    bpos[i] = j;
  }

  j = bpos[0];                          // case 2: prefix-of-pattern fallback
  for (i = 0; i <= m; i++) {
    if (shift[i] === 0) shift[i] = j;
    if (i === j) j = bpos[j];
  }
  return shift;
}

function boyerMooreSearch(text, pat) {
  const n = text.length, m = pat.length;
  if (m === 0 || m > n) return [];
  const last = lastOccurrenceTable(pat);
  const gs = goodSuffixTable(pat);
  const matches = [];
  let s = 0;
  while (s <= n - m) {
    let j = m - 1;
    while (j >= 0 && pat[j] === text[s + j]) j--;
    if (j < 0) {
      matches.push(s);
      s += gs[0];                       // shift for the next overlapping occurrence
    } else {
      const lastIdx = last.hasOwnProperty(text[s + j]) ? last[text[s + j]] : -1;
      const badCharShift = Math.max(1, j - lastIdx);
      const goodSuffixShift = gs[j + 1];
      s += Math.max(badCharShift, goodSuffixShift);
    }
  }
  return matches;
}

Pitfalls

The bad-character table must store the last occurrence of each character, not the first — using the first is a real, silent, checked bug. Building the table with for (let i = pat.length - 1; i >= 0; i--) table[pat[i]] = i (walking backward, so earlier — leftmost — indices overwrite later ones) looks like a harmless variation. It isn't: for text = "ccca", pat = "cca", the last-occurrence table gives {c: 1, a: 2} and the correct algorithm finds the real match at index 1 in two alignments. The first-occurrence table gives {c: 0, a: 2}; at the very first mismatch (pat[2] 'a' vs text[2] 'c'), the bad-character shift computes 2 - 0 = 2 instead of the correct 2 - 1 = 1 — one position too far — and the search jumps straight past s = 1 to s = 2, where s + m = 5 > n = 4 ends the loop having never checked the alignment that actually matches. Checked directly against naive search, not just reasoned about: the first-occurrence variant returns [] on this exact input; the correct one returns [1]. The rule exists to find the closest reusable occurrence behind the mismatch — using the first occurrence finds the farthest one instead, which overshoots.

The bad-character rule's max(1, ...) floor is easy to drop when implementing the rule in isolation — and simplified "Boyer-Moore" writeups that skip the good-suffix rule entirely are common enough that this is a real trap, not a hypothetical one. Without the floor, badCharShift = j - lastIdx goes non-positive whenever the mismatching character reoccurs in the pattern after position j. Checked: pattern "ab" against text = "bbbb" — the first comparison mismatches pat[0] 'a' against text[0] 'b' at j = 0; 'b''s last occurrence in the pattern is index 1, so the unfloored shift is 0 - 1 = -1, moving the window backward and never terminating. This page's implementation is protected from that specific case because the good-suffix shift is always ≥ 1 and the two are combined with max — but that protection only holds because both rules are present; an implementation using the bad-character rule alone needs the floor on its own merits.

Without Galil's rule, this algorithm has no linear worst-case guarantee — and the failure mode is checkable, not theoretical. Searching a thousand-character run of 'a' for a ten-character run of 'a': naive search takes 10,000 comparisons (n·m); this page's combined bad-character/good-suffix implementation takes 9,910 — barely better, not the roughly 1,010 an O(n+m) bound would promise. The cause: the pattern "aaaaaaaaaa" has a border of length 9 (everything but one character is both a prefix and a suffix), so gs[0] = 1 — after each of the 991 overlapping matches this input contains, the next alignment shifts by just one position and restarts its right-to-left comparison from the pattern's last character again, re-examining characters the just-found match already proved would match. This is precisely the redundant work Zvi Galil's 1979 rule removes: after a shift that follows an overlapping match, it tracks how much of the next window is already known-good and only compares the genuinely new characters, restoring a real linear worst-case bound. Not implemented on this page, named honestly rather than shipped as a false guarantee — see Complexity below.

Complexity

Time: preprocessing is O(m) for the bad-character table and O(m) for the good-suffix table (Gusfield's construction above, each pointer only moves forward). Search — best case O(n/m): when every alignment's first comparison (the pattern's last character) mismatches against a text character absent from the pattern entirely, the bad-character rule shifts by the full pattern length m every time, so as few as ⌈n/m⌉ alignments cover the whole text — the headline case for why Boyer-Moore often beats O(n+m) algorithms in practice on ordinary text. Search — worst case: not a proven linear bound, unlike KMP's unconditional O(n+m). As the Pitfalls section just showed with real numbers (9,910 comparisons searching a periodic pattern against equally periodic text, against naive search's own 10,000), a pattern that matches the text with heavy overlap defeats this implementation's shift rules almost entirely, because neither rule accounts for what the previous match already proved about the next alignment. Zvi Galil's 1979 addition (not implemented here) fixes exactly that gap and restores a genuine O(n+m) worst case. Space: O(min(m, Σ)) for the bad-character table (one entry per distinct pattern character, alphabet size Σ) plus O(m) for the good-suffix table — O(1) beyond that, excluding the match list; the text itself is never copied.

Two other algorithms already on this site solve the same exact-match problem with entirely different mechanisms: KMP compares left to right and reuses a failure-function table to guarantee no character is re-examined more than a bounded number of times, with no dependence on which characters are in play; Rabin-Karp skips character comparison almost entirely by comparing numeric fingerprints instead. Boyer-Moore's right-to-left scan and dual shift rules are a third, genuinely different angle — usually the fastest of the three in practice, at the cost of being the only one without an unconditional worst-case guarantee. A fourth, again completely different: Suffix Array doesn't scan the text against one pattern at all — it sorts the text's own suffixes once, up front, and answers any pattern decided later with a pair of binary searches instead of a pass over the text. See Choosing an Exact-Match String Matcher for how this page's practical speed weighs against the other nine exact-match entries.