↩ back to Exact Match

Galil's Rule

Boyer-Moore's own Pitfalls section names this gap directly: searching a thousand-character run of 'a' for a ten-character run of 'a', its combined bad-character/good-suffix implementation takes 9,910 character comparisons — barely better than naive search's 10,000, nowhere near the O(n+m) an amortized bound would promise. The cause: after each of the 991 overlapping matches that input contains, the next alignment re-examines characters the just-found match already proved would match. Galil's Rule (Zvi Galil, 1979) removes exactly that redundancy — not by changing either shift rule, but by remembering, after a match, how much of the next alignment is already known-good, and skipping comparison of that stretch entirely. On the same adversarial input, the version on this page needs 1,000 comparisons — a genuine O(n+m), not a marginal improvement.

Try it

Enter a text and a pattern (up to 30 and 12 characters). Step through: whenever an alignment starts with a trusted zone (dimmed cells at the low end of the pattern), those positions are skipped entirely — no comparison happens there, because the previous match already proved them. Only the fresh positions above the trusted zone are actually compared. The stats line tracks comparisons made here against what plain Boyer-Moore (no Galil's Rule) would have needed for the same alignments.

Why it works

When an alignment ends in a full match at position s, Boyer-Moore's own good-suffix table already gives the shift to try next: gs[0], the distance to the next place the whole pattern could plausibly recur. That value is not arbitrary — it is exactly the pattern's own smallest period: the least p such that pat[i] === pat[i + p] for every valid i. (For pat = "aaaaaaaaaa", every prefix of length 9 is also a suffix, so the longest border is 9 and the period is 10 − 9 = 1 — matching gs[0] = 1 exactly, checked directly against the shipped table below.)

That periodicity is the whole trick. Shifting by gs[0] to a new alignment s' = s + gs[0], the text in the range [s', s + m - 1] was already read during the match just found — it equals pat[gs[0] .. m-1], known without looking again. Because gs[0] is a genuine period of the pattern, pat[p] === pat[p + gs[0]] holds for every pattern position p from 0 up to m - 1 - gs[0] — so the text at those positions doesn't just equal some earlier pattern slice, it equals pat[p] itself. Comparing it again can only ever confirm what the period already guarantees. Only the newly-revealed tail — pattern positions above m - 1 - gs[0], the part the shift moved into view for the first time — actually needs a fresh look. That threshold is what this page's demo and reference implementation call memory: the count of low-end pattern positions, m − gs[0] of them, that the next alignment is allowed to skip.

This only works after a full match's shift, and the reference implementation below deliberately restricts it to that case (see Pitfalls for why generalizing the same skip to an ordinary mismatch-driven shift is unsound). A mismatch's good-suffix shift can come from two different cases — an interior recurrence of the matched suffix, or a fallback prefix match — and even when it comes from the first case, the safe region it guarantees sits in the middle of the new alignment, not anchored at position 0 the way the full-match case is. Reusing the same bottom-anchored memory formula there compares the wrong positions and trusts positions it never verified.

Reference implementation

Identical bad-character and good-suffix preprocessing to Boyer-Moore's own page — the only change is the memory variable, set only after a full match, and the scan's lower bound:

function lastOccurrenceTable(pat) {
  const table = {};
  for (let i = 0; i < pat.length; i++) table[pat[i]] = i;
  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;
  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];
  for (i = 0; i <= m; i++) {
    if (shift[i] === 0) shift[i] = j;
    if (i === j) j = bpos[j];
  }
  return shift;
}

function boyerMooreGalilSearch(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, memory = 0;
  while (s <= n - m) {
    let j = m - 1;
    while (j >= memory && pat[j] === text[s + j]) j--;
    if (j < memory) {
      // scanned down to (and including) memory with no mismatch — positions
      // [0, memory - 1] are guaranteed by the invariant above, no need to check them
      matches.push(s);
      const shift = gs[0];
      s += shift;
      memory = Math.max(0, m - shift);
    } 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);
      memory = 0; // conservative: only trust a carryover after a full match
    }
  }
  return matches;
}

Pitfalls

The scan's lower bound must be j >= memory, not j > memory — and the bug fires even on the very first alignment, before Galil's Rule has carried anything over. With memory initialized to 0, the intent of j >= memory is "compare every position, since nothing is known yet." Writing j > memory instead still lets the loop stop one position early: for text = "aba", pat = "bb", the first alignment compares only pat[1] against text[1] (both 'b', a match), then the loop condition 0 > 0 is false and stops — pat[0] is never checked against text[0], even though 'b' !== 'a', a real mismatch. The bug reports a full match at s = 0 that doesn't exist, then repeats the same one-off skip at s = 1, reporting two false matches ([0, 1]) where the correct answer is none. Checked directly against the naive-search oracle across 50,000 randomized trials: 37.0% wrong, not a rare edge case — any pattern whose last character happens to match is enough to trigger it.

Generalizing the memory skip to mismatch-driven shifts, not just full-match shifts, is a real correctness bug, not just an untried optimization. It's tempting: a mismatch at pattern index j also proves pat[j+1 .. m-1] matched, so why not compute a carryover the same way? Because the "Why it works" argument above only proves pat[p] === pat[p + shift] for positions anchored at the pattern's own start (p from 0) — that's specific to the full-match case, where the matched suffix is the whole pattern. For an ordinary mismatch at j < m - 1, the verified overlap after a shift sits at pattern positions [j + 1 - shift, m - 1 - shift] — a range in the middle of the pattern, not anchored at 0 — so a formula that skips positions [0, matchedLength - shift) is checking and skipping the wrong places. Concretely: text = "bbabbb", pat = "aabbb". The first alignment matches pat[3..4] ("bb") against text[3..4], mismatches at j = 2, and shifts by 1 (both rules agree). The generalized rule sets memory = 1 from that — but the second alignment's mismatch is really at pattern position 0 (pat[0] = 'a' against text[1] = 'b'), which memory = 1 wrongly treats as pre-verified and skips, reporting a phantom match at s = 1. Checked against the same oracle across 50,000 trials: 0.25% wrong — rarer than the boundary bug above, because it needs a mismatch whose shift happens to be small relative to its matched length, but just as real.

Complexity

Time: preprocessing is unchanged from Boyer-Moore, O(m) for each table. Search: exactly Boyer-Moore's own bounds on non-repetitive input — best case O(n/m), since Galil's Rule only ever activates after a full match and does nothing when matches are rare. On the specific pathology Boyer-Moore's own page names — a highly periodic pattern producing many overlapping matches — this page restores a genuine O(n+m): checked directly, 1,000 comparisons searching 1,000 'a's for ten 'a's, against the same input's 9,910 on Boyer-Moore's own unmodified page and 10,000 for naive search. On this page's own smaller default example (20 'a's, pattern of 10), naive search and plain Boyer-Moore need 110 comparisons each — identical, since a pattern this uniform gives neither shift rule anything to exploit — while the version here needs 20, an 82% reduction. Space: unchanged from Boyer-Moore, O(min(m, Σ)) for the bad-character table plus O(m) for the good-suffix table, plus one integer (memory).

Note what this page's scoped version does not claim: the general literature statement of Galil's Rule extends the same idea to mismatch-driven shifts too, via a proper interval tracked through every alignment, not just the single bottom-anchored threshold used here — the Pitfalls section above shows why that generalization needs real care to get right, and it isn't built on this page. The full-match case alone is enough to fix the exact pathology Boyer-Moore's own page names and measures, and restoring it here closes that page's forward reference honestly rather than half-doing the general case. See Choosing an Exact-Match String Matcher for how Boyer-Moore weighs against the site's other exact-match entries — this page is a refinement on that comparison, not a new branch in it.