Robert Boyer and J Strother Moore: Searching Text by Skipping Ahead
Robert Boyer and J Strother Moore reversed the usual direction of pattern comparison, using mismatches near the end of a pattern to skip large sections of text during exact search.
Most simple string searches begin at the left edge of the pattern
A straightforward matcher aligns a pattern with the text and compares from the beginning. If the first characters match but a later one fails, the algorithm may advance only slightly and repeat many comparisons.
Robert S. Boyer and J Strother Moore approached the alignment differently: compare from the pattern’s right end and use a mismatch to infer how far the whole pattern can jump.[1]
The direction of comparison changes the information available
A mismatch against the final portion of a pattern can rule out several future alignments at once. Boyer-Moore turns that information into skip distances rather than merely declaring the current alignment a failure.
The 1977 paper emphasized large jumps through the text
The original Communications of the ACM paper explains that matching begins with the last character of the pattern and that information from mismatches often allows the search to proceed in large jumps.[1]
This produces the algorithm’s counterintuitive practical property: on many texts it can locate a match without inspecting every preceding text character.
Longer patterns can create more opportunities to skip
A longer pattern carries more information about characters and suffixes. When that information disagrees with the text, the next plausible alignment may be several positions away rather than one.
The bad-character rule uses a mismatch to reject impossible alignments
If the text character causing a mismatch does not occur near the relevant part of the pattern, the pattern can be shifted past positions that could not possibly match. NIST summarizes Boyer-Moore as using mismatch information to jump to the next possible alignment.[2]
This rule is simple but powerful because it translates alphabet information into motion through the text.
Preprocessing turns the pattern into a skip table
Before searching, the algorithm records where characters occur in the pattern. The table is a compact summary of how far a mismatch permits the alignment to move.
The good-suffix rule uses structure in the matched tail
When a suffix of the pattern has already matched before an earlier mismatch, the algorithm can shift to another occurrence of that suffix or to a compatible prefix. This second rule exploits pattern structure rather than only the mismatching character.
Combining the character and suffix information produces much of Boyer-Moore’s practical power.
The algorithm learns from successful comparisons as well as failures
A partial suffix match is not wasted work. It constrains where a future full match can begin, allowing the search to preserve information while still jumping forward.
Boyer and Moore were also collaborators in automated reasoning
The authors’ publication records show that string search was one project within a long collaboration on theorem proving and program verification.[3][4]
That background helps explain the algorithm’s careful emphasis on what can be logically ruled out after each comparison rather than relying only on statistical intuition.
Later work refined the preprocessing and worst-case analysis
Boyer-Moore’s practical success stimulated detailed theoretical study. Wojciech Rytter published a corrected preprocessing algorithm in 1980, illustrating how an influential algorithm can remain subject to formal repair and clarification after its first publication.[5]
Other researchers established tighter worst-case bounds and variants, while the core right-to-left skip strategy remained recognizable.
Practical search depends on text, alphabet and pattern length
Boyer-Moore can outperform strict left-to-right methods when its skips are large, especially for longer patterns over reasonably rich alphabets. For very short patterns or unusual distributions, preprocessing and branch behavior may change the balance.
Its history therefore demonstrates the difference between worst-case guarantees and practical comparison counts. Both matter, but they answer different engineering questions.
Why Boyer-Moore belongs in coding history
Boyer and Moore showed that an algorithm can become faster by deliberately examining data in an unexpected order. Matching from the right creates information that a conventional left-to-right scan cannot exploit as aggressively.[1][2]
The deeper lesson is about negative information: a mismatch does more than say “not here.” Properly interpreted, it can eliminate many candidate positions at once.
Works Cited
- 01
- 02NIST Dictionary of Algorithms and Data Structures — Boyer-Moore xlinux.nist.gov
- 03
- 04
- 05
CodeHistory is a living archive. Citations document the evidence used for this edition; later evidence may refine the account.
Submit a research lead