Boyer–Moore: Search Backwards, Skip Forwards

Boyer–Moore is a string-matching algorithm built around a simple but powerful idea: do not inspect every possible alignment from left to right. Instead, align a pattern with part of the text, compare characters starting at the pattern’s right edge, and use a mismatch to decide how far the pattern can move forward.

That combination gives the algorithm its characteristic behavior. It searches backwards inside the current alignment so that it can skip forwards across the text. A mismatch is not merely a failure. It is evidence that several nearby alignments cannot work, so the algorithm jumps over them rather than checking them one by one.

The two rules emphasized here are:

• the bad-character rule, which uses the character that caused the mismatch;
• the good-suffix rule, which uses the suffix that matched before the mismatch.

The rules answer different questions. The bad-character rule asks where the mismatching text character could appear in the pattern. The good-suffix rule asks whether the suffix already matched can be aligned with another occurrence in the pattern, or with a suitable part of the pattern’s beginning.

The result is a search method that can often eliminate several candidate positions at once. The important skill is not memorizing a table, but understanding why a particular shift is safe.

The setting: a pattern moving across text​

Suppose the text is a sequence of characters and the pattern is the shorter sequence we want to find. For a small illustrative example, use this eight-character text:

TEXT:    A B C D A B C X
INDEX:   0 1 2 3 4 5 6 7

Let the pattern be:

PATTERN: A B C D
INDEX:   0 1 2 3

The pattern has four characters, so its first alignment covers text positions 0 through 3. The next alignment would cover positions 1 through 4, and so on. A straightforward approach might compare the pattern with each possible alignment from the leftmost pattern character. Boyer–Moore takes a different approach.

At an alignment beginning at text position 0, the pattern is placed like this:

TEXT:    A B C D A B C X
PATTERN: A B C D
         0 1 2 3

The comparison begins at the pattern’s rightmost character, D, rather than at its leftmost character, A.

Here the final characters match immediately:

TEXT:    A B C D A B C X
PATTERN: A B C D
                 ^

Then the comparison continues right to left. The C, B, and A also match, so the pattern is found at position 0. This is the successful case, but the main benefit of Boyer–Moore appears when a comparison fails.

Why begin at the right edge?​

Starting at the right edge makes a mismatch informative. Consider a pattern whose final character is unusual in the current region of text. If the rightmost comparison fails, there is no need to compare the pattern’s earlier characters at that alignment. More importantly, the mismatch can reveal that the pattern cannot match at several immediately following positions.

Use this illustrative pattern and text:

TEXT:    A B C X A B C D
PATTERN: A B C D

At the first alignment, the pattern covers the first four text characters:

TEXT:    A B C X A B C D
PATTERN: A B C D
                 ^

The pattern’s final character is D, while the text character under it is X. The comparison fails at the right edge. A left-to-right algorithm might already have compared A, B, and C before discovering the mismatch. Boyer–Moore discovers the mismatch first because it begins with D.

The mismatch is also useful because X does not occur anywhere in the pattern ABCD. If the pattern were shifted by only one position, the same text character X would still lie inside the pattern’s window, but it could not match any pattern character. The algorithm can therefore move the pattern beyond that occurrence instead of testing every intermediate alignment.

The exact movement is determined by a precomputed shift rule. This is the central distinction between ordinary comparison and Boyer–Moore: a mismatch can produce a shift, not just a restart.

Alignments and shifts​

An alignment is one placement of the pattern over a section of the text. If the pattern has length four, the first alignment begins at text index 0, the next possible alignment begins at index 1, then index 2, and so on.

A shift moves the pattern’s starting position to the right. For example:

First alignment:   text positions 0–3
Shift by 2:        text positions 2–5
Shift by 3:        text positions 3–6

A safe shift must not skip a genuine occurrence of the pattern. Boyer–Moore obtains safe shifts from information about the pattern and the mismatch. The bad-character and good-suffix rules may recommend different distances. When both are available, the algorithm uses the larger safe shift. A larger shift is useful because it removes more impossible alignments from consideration.

This does not mean that the pattern always leaps a large distance. Some mismatches produce a shift of one. The important point is that the algorithm has a reason for each movement and does not blindly repeat the same comparison process at every text position.

The bad-character rule​

The bad-character rule is based on the text character aligned with the mismatching pattern character. That text character is called the bad character for that comparison.

Imagine that the pattern is:

PATTERN: A B C D

Suppose the comparison proceeds from right to left and reaches this situation:

TEXT:    ... A B X D ...
PATTERN: ... A B C D
                  ^

The D characters matched. The next comparison is between text character X and pattern character C, and they mismatch. The bad character is X, because X is the text character involved in the mismatch.

The rule looks for the rightmost occurrence of X in the pattern, usually to the left of the mismatching pattern position. If such an occurrence exists, the pattern can be shifted so that this occurrence lines up with the text’s X. If X does not occur in the relevant part of the pattern, the pattern can move farther, past the bad character.

Bad character not present in the pattern​

Return to the illustrative example:

TEXT:    A B C X A B C D
PATTERN: A B C D

At the first alignment, the comparison is:

Text character:    X
Pattern character: D

The bad character is X. It does not appear anywhere in ABCD. Therefore, no alignment in which X lies under any position of the pattern can produce a match. The pattern can move far enough that the current X is no longer inside the pattern window.

The idea can be pictured as follows:

Before shifting:
TEXT:    A B C X A B C D
PATTERN: A B C D
               ^
             bad X

After shifting beyond X:
TEXT:    A B C X A B C D
PATTERN:         A B C D

The illustration is about the reasoning, not about a particular implementation’s table representation. The key fact is that X has no possible partner in the pattern. Testing alignments that keep X under the pattern would be wasted work.

Bad character occurs in the pattern​

Now use a pattern with a repeated character:

PATTERN: A B A C

Suppose a comparison fails at the pattern’s right side because the text contains A where the pattern expects C:

TEXT:    ... A B A A ...
PATTERN: ... A B A C

The bad character is A. The pattern already contains A earlier, at its second position from the left. A shift can line up that earlier A with the text’s mismatching A:

Text:       ... A B A A ...
Pattern:        A B A C
                         mismatch

The shift does not necessarily move the pattern past the bad character, because the bad character does occur in the pattern. Instead, it moves the pattern so that a plausible occurrence is aligned. The rightmost suitable occurrence is used because it generally permits the smallest safe movement that preserves a possible match.

If the bad character occurs only to the right of the mismatching pattern position, that occurrence cannot help with the current mismatch. The rule therefore uses an occurrence to the left of the mismatch, when one is available.

Why this avoids repeated work​

Without the bad-character rule, the search might move one text position at a time after every mismatch. With the rule, one mismatch can rule out multiple alignments. If a text character does not appear in the pattern, it immediately proves that the pattern cannot match while that character remains under the pattern window.

Even when the character does appear, the rule uses the pattern’s known character positions to avoid alignments that would force the same impossible comparison. It does not predict the future; it uses the current mismatch to identify positions that cannot possibly work.

The good-suffix rule​

The good-suffix rule uses a different kind of evidence. During a right-to-left comparison, some characters at the pattern’s right end may have matched before a mismatch occurred. That matched ending is called the good suffix.

For example, suppose the pattern is:

PATTERN: A B C D A B

During a comparison, perhaps the final two characters A B match, but the character before them fails:

TEXT:    ... ? ? ? A B
PATTERN: ... C D A B
                 ^
              mismatch here

The suffix AB is known to match the corresponding text characters. The question is: where else can the pattern’s suffix AB fit? If another occurrence of AB exists earlier in the pattern, the pattern can shift so that the already matched text AB aligns with that earlier occurrence.

The algorithm does not need to recheck the suffix immediately. The suffix has already been established as equal. Moving it to another compatible occurrence preserves that useful information.

A repeated good suffix​

Use this pattern:

PATTERN: A B A B

Suppose the final B matches, but the comparison fails at the preceding position:

TEXT:    ... X B
PATTERN: ... A B
             ^

The matched suffix is B. The pattern has another B earlier. A shift can align the known text B with that earlier pattern B, rather than discarding the match and starting over at the next text position.

For a longer suffix, the same principle applies. If the suffix AB matched and the pattern contains another AB, the algorithm can align the two copies. The already verified text is reused as evidence.

Matching a suffix with a prefix​

Sometimes the full good suffix does not occur elsewhere inside the pattern. A useful partial match may still exist between the suffix and the pattern’s prefix.

For example, consider a pattern with a structure like:

PATTERN: A B C A B

If the suffix AB has matched, that suffix is also equal to the pattern’s prefix AB. Even if there is no separate internal occurrence of the entire suffix, the pattern can shift so that the known suffix lines up with the beginning of the pattern.

This is useful because the suffix and prefix share the same characters. The shift retains the information already learned instead of treating the matched suffix as irrelevant.

The good-suffix rule therefore considers two broad possibilities:

1. align the matched suffix with another occurrence inside the pattern;
2. if that is not possible, align a matching suffix of the good suffix with a prefix of the pattern.

If neither possibility applies, the pattern must move far enough that the current matched suffix no longer creates a false expectation about a match. The exact shift depends on the pattern’s structure.

Bad character and good suffix together​

The two rules are complementary. The bad-character rule focuses on one mismatching text character. The good-suffix rule focuses on a sequence that matched before the mismatch.

Consider this general comparison:

TEXT:       ... p q r s t ...
PATTERN:    ... p q X s t
                    ^

Working from right to left, t and s match. The comparison then fails between text character r and pattern character X.

• The bad character is r.
• The good suffix is st.

The bad-character rule checks where r occurs in the pattern. The good-suffix rule checks where st, or a suitable part of it, can be aligned in the pattern. Each rule may produce a different safe shift.

The algorithm chooses the larger shift. Each rule describes a movement that does not discard a possible match. If one rule permits a shift of two and the other permits a shift of four, moving by four is still safe according to both rules: it is far enough for each independent argument.

This combination is the heart of Boyer–Moore. One rule uses the mismatch, and the other uses the successful comparisons immediately before it. The algorithm takes advantage of both kinds of information from the same attempt.

A complete small walk-through​

Use an eight-character text and a four-character pattern:

TEXT:    A B C X A B C D
INDEX:   0 1 2 3 4 5 6 7
PATTERN: A B C D

Alignment 1: text positions 0 through 3​

Place the pattern over the first four text characters:

TEXT:    A B C X A B C D
PATTERN: A B C D
                 ^

Compare from right to left. The first comparison is between pattern character D and text character X. They differ immediately.

The bad character is X. Because X does not occur in the pattern, an alignment that keeps X under the pattern cannot succeed. The pattern can move beyond this X.

There is no good suffix here because the first comparison, at the right edge, failed. The bad-character evidence is enough to make a large movement.

Alignment 2: near the end of the text​

After shifting beyond X, the pattern is aligned with the final four characters:

TEXT:    A B C X A B C D
PATTERN:         A B C D

Now compare from right to left:

Text:       A B C X A B C D
Pattern:            A B C D
                         ^

The final D matches the final D. Then C matches, B matches, and A matches. All four characters agree, so the pattern occurs starting at text position 4.

This example is deliberately small, but it demonstrates the essential saving. The search does not need to test alignments beginning at positions 1, 2, and 3. The character X rules them out for the pattern ABCD.

Preprocessing: preparing the pattern​

Boyer–Moore relies on information about the pattern’s characters and repeated substrings. That information can be prepared before the text scan begins.

For the bad-character rule, the preparation records where pattern characters occur, especially the rightmost useful occurrence. With a pattern such as:

A B A C A

the repeated A characters matter. When a mismatch involves A, the algorithm needs to know which occurrence can produce the appropriate shift.

For the good-suffix rule, the preparation records how suffixes of the pattern relate to other internal occurrences and to prefixes. A suffix is not merely a substring selected in advance; it is the portion that has actually matched immediately before a mismatch. The preprocessing makes it possible to look up a safe movement for that matched portion.

The tables are normally built from the pattern, not from the entire text. Once prepared, they can be reused while the pattern is compared with the text. This separation is useful when the same pattern is searched in more than one text, because the pattern’s structure does not change.

The conceptual workflow is:

1. inspect the pattern;
2. prepare bad-character information;
3. prepare good-suffix information;
4. align the pattern with the text;
5. compare from right to left;
6. on a mismatch, calculate the rule-based shifts;
7. move by the larger safe shift;
8. repeat until the pattern is found or no full alignment remains.

The key practical point is that preprocessing converts repeated structural questions into quick decisions during the scan.

Search backwards, skip forwards​

The title captures a useful mental model:

• Search backwards: compare the pattern from its right edge toward its left edge.
• Skip forwards: when a mismatch appears, move the pattern to a later alignment, often skipping several candidate positions.

These two actions are connected. Comparing from the right edge makes the last text character examined especially informative. If it does not match, the algorithm may be able to discard a large region. If it does match, the algorithm continues left and may discover a long good suffix that can also guide the shift.

A left-to-right comparison often finds a mismatch after spending work on the pattern’s beginning. Boyer–Moore tries to make a mismatch happen early in the comparison by examining the right side first. The mismatch then supplies the information needed for a jump.

This is not a claim that every input produces a large jump. Repeated characters or particular pattern arrangements can limit the available shift. The strength of the method comes from using available structure when it exists, while still maintaining a safe search.

What can go wrong in an implementation?​

The rules are simple to describe but must be applied carefully.

First, a shift must never skip a real occurrence. A bad-character table must distinguish between occurrences that are useful for the current mismatch position and occurrences that lie on the wrong side. A good-suffix table must correctly account for both internal occurrences and compatible prefixes.

Second, the comparison direction must agree with the table definitions. If the implementation compares from right to left but treats a suffix as though it had been matched from left to right, its shift calculations can be incorrect.

Third, a full match is different from a mismatch. When every pattern character matches, the search has found an occurrence. If the task is to find later occurrences too, another shift is needed after the match. That shift must preserve the possibility of overlapping matches.

For example, a pattern can overlap with another copy of itself. A search procedure that always moves by the full pattern length after a match could miss such an occurrence. The good-suffix or related pattern-structure information is relevant to preserving those possibilities.

Finally, small examples should be traced with indexes. Writing the text and pattern on separate lines, marking the mismatch, naming the bad character, and naming the good suffix makes off-by-one errors much easier to detect.

Complexity and trade-offs​

The explanation here establishes the comparison direction and the two shift rules, but it does not specify a formal time or space bound for a particular implementation. Complexity therefore depends on the exact Boyer–Moore variant and on how its tables are represented.

The practical trade-off is clear from the method itself:

• preprocessing requires additional work before the scan;
• the prepared information occupies additional space;
• in return, the search can skip alignments instead of checking every one in the same way.

A simple bad-character table may be organized around the set of possible text characters. A more compact representation can store only characters that occur in the pattern, but lookup details depend on the implementation and character encoding. The good-suffix data also requires storage for pattern-related shifts.

For a single very short search, preprocessing may be a noticeable part of the total work. For repeated searches with the same pattern, the preparation can be reused, making the shift information more valuable. The best choice depends on the pattern, text, character set, and whether the pattern is searched once or many times.

The algorithm is especially attractive when a mismatch can eliminate many alignments. When the pattern contains repeated characters or the input causes frequent small shifts, the benefit may be less dramatic. The correct takeaway is not that Boyer–Moore always jumps far, but that it is designed to exploit evidence that simpler scanning would throw away.

Practical uses in text search​

The same reasoning is useful in systems that search text for a known query. A text-search feature can align a query with a document, compare from the query’s right edge, and use mismatch information to move through the document. The larger the document relative to the pattern, the more valuable it can be to avoid examining every possible starting position in exactly the same way.

In a search box, the situation may involve more than one algorithmic concern. Text may need to be normalized, a query may change after each keystroke, and results may need ranking. Boyer–Moore addresses the specific task of finding a fixed pattern inside text. If the query remains unchanged while many text regions are searched, reusing the pattern’s prepared information is a natural fit.

For autocomplete, the central operation is often prefix lookup: the user types the beginning of a word, and the system finds entries sharing that beginning. That is a different shape of problem from locating an arbitrary pattern inside a finished text. Boyer–Moore’s backward comparison and shift rules are most directly relevant when the task is substring matching. The distinction matters: an algorithm should be chosen for the structure of the query and the required result, not only because it is associated with text.

For document search, the bad-character rule can be particularly intuitive. If a character under the pattern cannot occur in the pattern at all, it can separate the current window from possible matches. The good-suffix rule is helpful when the query has repeated substrings, because matched endings can be reused when deciding where the next alignment belongs.

A checklist for reading a Boyer–Moore trace​

When following an example, ask these questions in order:

1. Where is the pattern currently aligned?
2. Which pattern index is being compared first?
3. Which characters matched while moving from right to left?
4. At which pair did the mismatch occur?
5. What is the bad character from the text?
6. What suffix of the pattern has already matched?
7. Where could the bad character occur in the pattern?
8. Where could the good suffix occur, or which prefix could align with it?
9. What shift does each rule justify?
10. Which larger safe shift should be used?

For the eight-character example, the trace is short enough to perform by hand. The first right-edge comparison sees X versus D. Since X is absent from ABCD, the pattern moves beyond X. At the later alignment, the right edge matches, and the remaining characters are checked from right to left until the complete pattern is confirmed.

This checklist also explains why the algorithm is more than a clever comparison order. Every skipped alignment has a justification derived from the mismatch, the matched suffix, or both.

Practical takeaways​

Boyer–Moore can be remembered through five ideas:

1. Align a pattern with the text. The search considers possible starting positions, but it does not have to inspect them all individually.
2. Compare from right to left. The pattern’s right edge is checked first so that a mismatch can provide useful shift information.
3. Use the bad-character rule. Find where the mismatching text character could fit in the pattern, or move beyond it if it cannot fit at all.
4. Use the good-suffix rule. Preserve the work represented by a suffix that already matched by aligning it with another occurrence or a compatible prefix.
5. Take the larger safe shift. Both rules help eliminate impossible alignments; the larger justified movement skips more work.

The method’s central lesson is broadly useful in algorithm design: a failed comparison can contain information. Instead of throwing that information away and restarting one position later, Boyer–Moore uses it to decide where the next meaningful comparison should begin.

When you see the pattern moving forward by more than one character, ask what evidence made the skipped positions impossible. When you see comparisons beginning at the right edge, ask what a right-side mismatch can reveal about the surrounding text. Those questions lead directly to the bad-character and good-suffix rules—and to the distinctive strategy behind Boyer–Moore: search backwards, skip forwards.