Boyer-Moore

Strings O(n/m) best O(σ)

Compares the pattern right to left and uses the bad-character table to leap past hopeless alignments — often sublinear in practice.

pattern

A00

B·1

C·2

TextPattern

i=0

1/45

last['A'] = 0 — rightmost occurrence so far.

InvariantComparing right to left means a mismatched character that does not occur in the pattern lets the whole pattern skip past it.

pointermatchmismatchwindow

boyer-moore.c

#define R 256
 
void badChar(const char *p, int m, int last[R]) {
    for (int c = 0; c < R; c++) last[c] = -1;
    for (int i = 0; i < m; i++)
        last[(int)p[i]] = i;
}
 
void boyerMoore(const char *t, const char *p) {
    int n = strlen(t), m = strlen(p);
    int last[R];
    badChar(p, m, last);
 
    int s = 0;
    while (s <= n - m) {
        int j = m - 1;
        while (j >= 0 && p[j] == t[s + j])
            j--;
        if (j < 0) {
            printf("found at %d\n", s);
            s += 1;
        } else {
            int shift = j - last[(int)t[s + j]];
            s += shift > 1 ? shift : 1;
        }
    }
}

How Boyer-Moore works

Compare the pattern right to left. On a mismatch, the bad-character rule slides the pattern so its last occurrence of the offending text character lines up — often skipping many positions in one jump.

Best case

Alphabet-rich text: about n/m character looks — sublinear.

Worst case

Degenerate repetitive inputs: O(n·m) for the bad-character-only variant.

When to use it

Long patterns over large alphabets: text editors' find, grep-style scanning.