Boyer-Moore Visualizer

Visualize right-to-left comparisons and bad-character shifts in Boyer-Moore string search with interactive playback and metrics.

Current status: Ready. Use the controls to begin exploring Boyer-Moore.

Boyer-Moore Algorithm Visualizer

T
H
I
S
I
S
A
T
E
S
T
T
E
X
T
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
T
E
S
T

Compare pattern[3] = 'T' with text[3] = 'S'.

Bad Character Table:
T: 3
E: 1
S: 2
Step 1 / 26

Animation Legend

Comparing Now
Mismatch (triggers shift)
Full Match

Unlike most string search algorithms, Boyer-Moore compares the pattern against the text from right to left. When it hits a mismatch, the bad character rule looks up where that text character last occurs in the pattern and jumps the pattern forward to align with it - often skipping several positions in a single move.

Java Implementation

public List<Integer> boyerMoore(String text, String pattern) {
    int n = text.length(), m = pattern.length();
    Map<Character, Integer> badChar = new HashMap<>();
    for (int i = 0; i < m; i++) badChar.put(pattern.charAt(i), i);

    List<Integer> matches = new ArrayList<>();
    int s = 0;
    while (s <= n - m) {
        int j = m - 1;
        while (j >= 0 && pattern.charAt(j) == text.charAt(s + j)) {
            j--;
        }
        if (j < 0) {
            matches.add(s);
            s += 1;
        } else {
            int lastOccurrence = badChar.getOrDefault(text.charAt(s + j), -1);
            s += Math.max(1, j - lastOccurrence);
        }
    }
    return matches;
}
Best Case: O(n / m)
Worst Case: O(n * m)

What is the Boyer-Moore Algorithm?

Boyer-Moore searches for a pattern by comparing it against the text starting from the rightmost character instead of the leftmost. This flips the usual intuition: on a mismatch, the algorithm often already knows enough to skip multiple positions at once, rather than sliding forward by just one.

This demo implements the bad character rule: when a mismatch occurs, it looks up the last position of the mismatched text character within the pattern and shifts the pattern to align with it. The full algorithm also uses a good suffix rule for even larger jumps, giving Boyer- Moore its reputation as one of the fastest general-purpose string search algorithms in practice - often faster than KMP on natural-language text with a large alphabet.

Time & Space Complexity

  • Best CaseO(n / m)
  • Worst CaseO(n · m)
  • Space (Bad Char Table)O(alphabet size)

* Sub-linear best case: not every text character needs to be inspected.

Real-World Use Cases

  • ✓
    grep and Text EditorsMany Unix search tools use Boyer-Moore or its variants for fast literal search.
  • ✓
    Antivirus Signature ScanningQuickly skipping over large files while searching for known byte signatures.
  • ✓
    Large-Alphabet SearchPerforms best when the alphabet is large relative to the pattern length, like natural language text.

Concept guide

Review the mental model, tradeoffs, and practical use cases after you experiment.

Boyer-Moore Algorithm Complete Info Card

String MatchingSub-Linear Best Case

Boyer-Moore compares the pattern right to left and uses the bad character rule to skip large sections of text in a single move whenever a mismatch occurs.

Algorithm Characteristics

Best Case Time

Sub-linear: not every character needs inspecting

O(n / m)

Worst Case Time

Rare in practice with a reasonable alphabet size

O(n · m)

Space Complexity

One table entry per distinct character

O(alphabet)

Comparison Direction

Unusual among string search algorithms

Right to Left

Core Technique

Skip ahead using the mismatched character's position

Bad Character Rule

Extra Optimization

Not shown here, but combines with bad character in practice

Good Suffix Rule

Algorithm Steps

1

Build a table of each character's last position in the pattern

2

Align the pattern at the start of the text

3

Compare pattern and text from the rightmost character leftward

4

On a full match, record it and shift by one

5

On a mismatch, look up the bad character's last pattern position

6

Shift the pattern forward by the computed amount and repeat

When to Use

  • •Large alphabets, like natural-language text
  • •Long texts where average-case speed matters most
  • •Command-line search tools and antivirus signature scanning

When to Avoid

  • •Very small alphabets, like binary or DNA (fewer skips)
  • •Guaranteed worst-case linear time is required (use KMP)
  • •Very short patterns, where setup cost outweighs the benefit
Did You Know? The Unix grep command and many text editors' "find" features are built on Boyer-Moore-style algorithms because of their strong average-case performance on real text.
Bad character ruleRight-to-left scangrep