A line scanner looks for ERROR in English logs. Naive and KMP start at the left of the window. Most mismatches happen on the last letter you check if you start at the right: the window ends in g and the pattern ends in R, so you can jump until that g lines up with an R in the pattern — or skip the whole pattern if g never appears.

Boyer-Moore compares from the end of the pattern; the bad-character rule (and good-suffix) say how far to shift on a miss. Best case on a large alphabet is sublinear in the text: you never read every character. Worst case still exists; it is not KMP’s linear guarantee.

This post is the skip. LPS that never retreats the text is KMP. Rolling hashes are Rabin-Karp. Many needles: Aho-Corasick. Catalog: Algorithms Roadmap.

Compare from the right

Align pattern at text[i .. i+m). Read j from m-1 down to 0. A full match returns i. A mismatch at j consults a skip table and increases i.

The rule this post implements fully is bad character: look at the haystack character that missed. Shift so that character lines up with its rightmost occurrence in the pattern, or shift by m if it never occurs.

static int[] badCharTable(char[] p) {
    int[] skip = new int[256];
    Arrays.fill(skip, -1);
    for (int i = 0; i < p.length; i++) {
        skip[p[i] & 0xFF] = i;
    }
    return skip; // last index of each byte, or -1
}

static int indexOfBm(String text, String pattern) {
    if (pattern.isEmpty()) {
        return 0;
    }
    char[] t = text.toCharArray();
    char[] p = pattern.toCharArray();
    int n = t.length;
    int m = p.length;
    int[] last = badCharTable(p);
    int i = 0;
    while (i + m <= n) {
        int j = m - 1;
        while (j >= 0 && t[i + j] == p[j]) {
            j--;
        }
        if (j < 0) {
            return i;
        }
        int bc = last[t[i + j] & 0xFF];
        i += Math.max(1, j - bc);
    }
    return -1;
}

j - last[c] is how far to slide so c under the mismatch lines up with its last pattern index. If last[c] > j, a naive subtract would go backward — Math.max(1, …) keeps the scan moving. Full Boyer-Moore also computes a good-suffix table (how far to shift when a suffix of the pattern already matched). Horspool is the popular simplification: always skip using the last window character, not the mismatch index. Interviewers want the idea (end-first, skip by the missing character). Production ports usually ship Horspool or a tuned memmem.

Note: The table above is bytes. UTF-16 char above 255 needs a map, not an array of 256. String.indexOf is still the default for one String needle.

A walk: mismatch at the end

text    = FINDINHAY
pattern = NEED
m = 4

i=0 window FIND  compare D vs D? F≠D  last[F]=-1  shift 4
i=4 window INHA  compare A vs D? A≠D  last[A]=-1  shift 4
i=8  8+4 > n  miss

Almost no characters of the haystack were compared. That is the large-alphabet win. Hostile periodic patterns (AAA… in AAA…) can still compare every position; then KMP’s worst-case bound is the honest contract.

When not to use Boyer-Moore

  • Tiny alphabet, highly periodic needle. Worst-case compares pile up. Prefer KMP.
  • You needed a hash reject. Rabin-Karp.
  • Many needles. One skip table per pattern still multiplies scans. Aho-Corasick.
  • You implemented only bad-character and called it full BM. Say Horspool. Good-suffix is a second table.

Cheat sheet

Job:       exact match; skip when the window's end cannot fit
Compare:   from pattern end toward start
Bad char:  shift so mismatched text char aligns with last occurrence in pattern
Good suffix: extra table (full BM); Horspool uses last window char only
Best:      sublinear on large alphabets     Worst: not better than naive
JDK:       String.indexOf; write BM on your own buffers
Not this:  KMP linear worst case; Aho-Corasick dictionary

Do:

  • Build last[c] as the rightmost index of c in the pattern.
  • Shift at least 1. Never decrement i.
  • Prefer KMP when you must quote a linear worst case.

Don’t:

  • Use a 256-slot table on arbitrary UTF-16 without masking or a map.
  • Claim O(n/m) as a guarantee.
  • Skip the character-by-character confirm of a “match.”

Wrap-up

Boyer-Moore starts at the end of the window so a mismatch can jump the haystack by more than one. The bad-character table is the skip you can write in an interview. Good-suffix is the rest of the original paper. Sublinear is typical on English; linear worst-case is KMP’s job.

The layout was already a string. The procedure is end-first plus a skip. When the job is every needle in a dictionary, one automaton is cheaper than one skip table per word — Aho-Corasick.

Next optional step in the series Many patterns, one pass over the text. Aho-Corasick: Many Patterns, One Pass Over the Text