Boyer Moore Algorithm for Pattern Searching

The problem, simply

You get a long text of length n and a short pattern of length m. Give back every starting spot in the text where the pattern appears.

The Boyer Moore way does this with two surprises. It compares the pattern from its right end, not its left. And when a letter does not match, it uses that wrong letter to decide how far the pattern can jump, often many spots at once.

A story to remember it

Picture it

Examples

Way 1: the simple way

Put the pattern at spot 0 and compare letter by letter. Then move it one spot to the right and do it again, all the way to the end.

1. For every start s from 0 to n - m:
2. Compare pattern[j] with text[s + j] for j = 0, 1, 2, ....
3. If all m letters match, write down s.

import java.util.*;

class Solution {
    public List<Integer> search(String text, String pat) {
        List<Integer> found = new ArrayList<>();
        int n = text.length(), m = pat.length();
        for (int s = 0; s + m <= n; s++) {       // every start spot
            int j = 0;
            while (j < m && text.charAt(s + j) == pat.charAt(j)) j++;
            if (j == m) found.add(s);           // all letters matched
        }
        return found;
    }
}

How long it takes: up to n start spots, and up to m letter checks at each, O(n * m). Text AAAA...A with pattern AAAB hits that worst case. Extra room: O(1) besides the answer.

Way 2: the clever way

This is the bad character rule of Boyer Moore.

1. Before searching, fill a small table: for every letter, the last spot where it appears in the pattern. Letters not in the pattern get -1.
2. Put the pattern at shift s = 0. Compare from the right end, j = m - 1, moving left while the letters match.
3. If every letter matched, write down s. Then look at the text letter just after the pattern and slide so that the pattern's last copy of that letter sits under it: s += m - last[text[s + m]]. If the text has ended, slide 1.
4. If there is a mismatch at j, call the text letter there the bad letter. Slide by j - last[bad], so the pattern's last copy of the bad letter sits under it. If that number is 0 or negative, slide 1 instead.

import java.util.*;

class Solution {
    public List<Integer> search(String text, String pat) {
        List<Integer> found = new ArrayList<>();
        int n = text.length(), m = pat.length();
        if (m == 0 || m > n) return found;

        int[] last = new int[256];          // last spot of each letter in the pattern
        Arrays.fill(last, -1);
        for (int i = 0; i < m; i++) last[pat.charAt(i)] = i;

        int s = 0;                          // where the pattern starts now
        while (s <= n - m) {
            int j = m - 1;                  // compare from the right end
            while (j >= 0 && pat.charAt(j) == text.charAt(s + j)) j--;
            if (j < 0) {
                found.add(s);
                // line up the letter just after the pattern, or move 1 at the end
                s += (s + m < n) ? m - last[text.charAt(s + m)] : 1;
            } else {
                // line up the bad letter with its last copy in the pattern
                s += Math.max(1, j - last[text.charAt(s + j)]);
            }
        }
        return found;
    }
}

How long it takes: when the bad letters are often missing from the pattern, every check jumps m spots, so only about n / m alignments are looked at. That is faster than reading the whole text. In the worst case, like text AAAA...A and pattern BAAA, the jumps are tiny and it falls back to O(n * m). Extra room: one table entry per letter of the alphabet, O(k), which is 256 here.

Way 3: add the good suffix rule

Full Boyer Moore has a second rule. When the right part of the pattern already matched before the mismatch, look for another copy of that matched tail earlier in the pattern, and slide so that copy sits under the same text letters. If there is none, slide so that the longest front piece of the pattern that equals a back piece lines up. Take the bigger of the two jumps.

With both rules, finding the first match takes linear time, O(n + m), and long jumps are common, which is why text editors and grep like it. Reporting every match can still be slow on texts like AAAA...A unless you add one more trick, the Galil rule.

import java.util.*;

class Solution {
    public List<Integer> search(String text, String pat) {
        List<Integer> found = new ArrayList<>();
        int n = text.length(), m = pat.length();
        if (m == 0 || m > n) return found;

        int[] last = new int[256];
        Arrays.fill(last, -1);
        for (int i = 0; i < m; i++) last[pat.charAt(i)] = i;

        // good suffix table: shift[j] = how far to slide when pat[j..] matched
        int[] shift = new int[m + 1];
        int[] border = new int[m + 1];
        int i = m, j = m + 1;
        border[i] = j;
        while (i > 0) {
            while (j <= m && pat.charAt(i - 1) != pat.charAt(j - 1)) {
                if (shift[j] == 0) shift[j] = j - i;
                j = border[j];
            }
            i--; j--;
            border[i] = j;
        }
        j = border[0];
        for (i = 0; i <= m; i++) {
            if (shift[i] == 0) shift[i] = j;
            if (i == j) j = border[j];
        }

        int s = 0;
        while (s <= n - m) {
            int k = m - 1;
            while (k >= 0 && pat.charAt(k) == text.charAt(s + k)) k--;
            if (k < 0) {
                found.add(s);
                s += shift[0];
            } else {
                int bad = k - last[text.charAt(s + k)];
                s += Math.max(bad, shift[k + 1]);   // the bigger safe jump wins
            }
        }
        return found;
    }
}

Watch out for

• A table of size 256 only works for plain letters. For any Unicode text use a HashMap<Character, Integer> or an array of size 65536.
• After a full match, do not jump by m. Overlapping matches like AA in AAAAA would be lost.
• Check m > n and the empty pattern first.
• Comparing from the left with Boyer Moore jumps gives wrong jumps. The rules assume the right end is checked first.

What interviewers ask next

• How does it compare with KMP? KMP never re-reads a text letter and is always O(n + m). Boyer Moore can skip letters entirely, so on long texts with a big alphabet, like English, it is usually faster in practice.
• When is the bad character rule weak? With tiny alphabets like DNA (A, C, G, T) almost every letter is in the pattern, so jumps are short. The good suffix rule helps there.
• What is Horspool's version? It always uses the text letter under the pattern's last spot to decide the jump, even after a partial match. It is simpler and almost as fast.
• How would you search for many patterns at once? Build a trie of all patterns and use Aho Corasick, or use a rolling hash (Rabin Karp) for many patterns of the same length.

Remember this

Grown-up words: the stencil card is the pattern window, sliding it is the shift, the wrong letter is the bad character, the table of last spots is the bad character table, the matched tail is the good suffix, and reading fewer than n letters is sublinear average time.