01 / The idea
One marker does not need one comparison per position.
Boyer–Moore searches for one exact pattern by aligning it under the text and comparing from right to left. When a comparison fails, the mismatch and any suffix that already matched tell us how far the pattern can move without skipping a possible occurrence.
For a short marker, the built-in string search may be the better production choice. This lesson makes the decision visible: compile reusable skip tables, trace each alignment, and return every exact hit with positions that agree across TypeScript and Go.
For the fixed report, the marker appears at scalar ranges 26–31, 58–63, and 81–86. The end is exclusive, so the first hit covers
five positions from 26 through 30.
02 / Name the rule
Two skip rules make one alignment useful.
shift = max(bad-character shift, good-suffix shift, 1)
The bad-character table stores the rightmost pattern position for each symbol. If the document symbol at the mismatch occurs farther left in the marker, line that occurrence up; if it is absent, move past it. The good-suffix table uses the suffix that matched at the right edge: line that suffix up with another copy, or with a matching prefix.
Comparing right to left matters because the right edge often disagrees immediately. A five-symbol marker can reject a window after one check and move five positions, while a left-to-right scan would learn the same fact only after trying a different starting position.
Remember the marker
Compile once; repeated documents reuse the same two tables.
Start at the right
Record the matched suffix and stop at the first right-to-left mismatch.
Keep every possibility
Take the larger safe move, with a minimum of one, then continue until the text ends.
Why can the pattern move so far?The skipped windows cannot match
A shift is safe because it is derived from a necessary condition for a future match. The bad character says where the observed symbol could line up in the marker. The good suffix says what a future marker must do with the suffix already confirmed. Taking the larger of them preserves the stronger proof; the fallback of one keeps the scan moving.
03 / Follow one operation
Watch the cursor jump, then confirm the whole marker.
The animation replays the real search. It starts with the first alignment, shows the right-to-left comparison order, groups the safe skips, and finishes on all three hits. It teaches the moves; it makes no claim about wall-clock speed.
Skip the text that cannot start the marker.
A right-to-left mismatch allowed a 5-symbol skip.
confirmed marker mismatch ordinary document text
Align at the right edge
Line up “retry” at the start of the document and compare from its right edge. An early mismatch can reject the whole window after a single symbol check.
Reduced motion: choose a scene to see its completed state.
Read this scene
Line up “retry” at the start of the document and compare from its right edge. An early mismatch can reject the whole window after a single symbol check.
Alignments shown: 1 of 24. At offset 0, the comparison stopped at pattern index 4 on “i”; shift by 5.
Watch and Step through replay the same right-to-left comparisons. Try it runs the TypeScript search on edited text and pattern inputs.
04 / Read the shape
The tables are the reusable boundary.
Basic form validates a marker and builds both tables. In the wild walks one document and records alignments. At the call site compiles retry once, searches the report, and formats half-open hit ranges. The complete example
prints the same receipt a caller can test.
Validate one marker and prepare its last-occurrence and good-suffix tables. The pattern is compiled once so repeated documents reuse the same work.
export const MAX_PATTERN_SCALARS = 32;
export const MAX_TEXT_SCALARS = 512;
export type Hit = { start: number; end: number };
export type Alignment = {
offset: number;
comparisons: number[];
mismatchIndex: number | null;
mismatchSymbol: string | null;
matchedSuffixLength: number;
shift: number;
hit: boolean;
};
export type CompiledPattern = {
pattern: string;
symbols: string[];
badCharacter: Map<string, number>;
goodSuffix: number[];
};
export type SearchResult = {
pattern: string;
text: string;
hits: Hit[];
alignments: Alignment[];
};
export type SearchErrorCode = 'empty-pattern' | 'long-pattern' | 'long-text' | 'malformed-text';
export class SearchError extends Error {
readonly code: SearchErrorCode;
constructor(code: SearchErrorCode, message: string) {
super(message);
this.name = 'SearchError';
this.code = code;
}
}
function scalars(value: string, limit: number, code: SearchErrorCode, label: string): string[] {
const symbols = Array.from(value);
for (const symbol of symbols) {
const point = symbol.codePointAt(0)!;
if (point >= 0xd800 && point <= 0xdfff)
throw new SearchError('malformed-text', `${label} must be well-formed Unicode.`);
}
if (symbols.length > limit)
throw new SearchError(code, `${label} is limited to ${limit} Unicode scalar values.`);
return symbols;
}
function buildBadCharacter(symbols: string[]): Map<string, number> {
const table = new Map<string, number>();
for (const [index, symbol] of symbols.entries()) table.set(symbol, index);
return table;
}
// Strong good-suffix preprocessing. shift[r] is the distance after a mismatch at r - 1
// (shift[m] covers a mismatch on the last symbol, with nothing matched yet).
// shift[0] is the pattern's period: the shortest move after a complete match that can
// still line up an overlapping occurrence.
function buildGoodSuffix(symbols: string[]): number[] {
const length = symbols.length;
const shift = new Array<number>(length + 1).fill(0);
const border = new Array<number>(length + 1).fill(0);
let i = length;
let j = length + 1;
border[i] = j;
while (i > 0) {
while (j <= length && symbols[i - 1] !== symbols[j - 1]) {
if (shift[j] === 0) shift[j] = j - i;
j = border[j];
}
i -= 1;
j -= 1;
border[i] = j;
}
j = border[0];
for (i = 0; i <= length; i += 1) {
if (shift[i] === 0) shift[i] = j;
if (i === j) j = border[j];
}
return shift;
}
export function compile(pattern: string): CompiledPattern {
const symbols = scalars(pattern, MAX_PATTERN_SCALARS, 'long-pattern', 'The pattern');
if (symbols.length === 0) throw new SearchError('empty-pattern', 'The pattern cannot be empty.');
return {
pattern,
symbols,
badCharacter: buildBadCharacter(symbols),
goodSuffix: buildGoodSuffix(symbols)
};
}// Boyer–Moore substring search with bad-character and good-suffix shifts.
const (
MaxPatternScalars = 32
MaxTextScalars = 512
)
type Hit struct {
Start int
End int
}
type Alignment struct {
Offset int
Comparisons []int
MismatchIndex int
MismatchSymbol string
MatchedSuffixLength int
Shift int
Hit bool
}
type CompiledPattern struct {
Pattern string
Symbols []rune
BadCharacter map[rune]int
GoodSuffix []int
}
type SearchResult struct {
Pattern string
Text string
Hits []Hit
Alignments []Alignment
}
type SearchError struct {
Code string
Message string
}
func (e *SearchError) Error() string { return e.Message }
func symbols(value string, limit int, code string, label string) ([]rune, error) {
if !utf8.ValidString(value) {
return nil, &SearchError{Code: "malformed-text", Message: fmt.Sprintf("%s must be well-formed UTF-8", label)}
}
result := []rune(value)
if len(result) > limit {
return nil, &SearchError{Code: code, Message: fmt.Sprintf("%s is limited to %d Unicode scalar values", label, limit)}
}
return result, nil
}
func buildBadCharacter(pattern []rune) map[rune]int {
table := make(map[rune]int, len(pattern))
for index, symbol := range pattern {
table[symbol] = index
}
return table
}
// Strong good-suffix preprocessing. shift[r] is the distance after a mismatch at r - 1
// (shift[m] covers a mismatch on the last symbol, with nothing matched yet).
// shift[0] is the pattern's period: the shortest move after a complete match that can
// still line up an overlapping occurrence.
func buildGoodSuffix(pattern []rune) []int {
length := len(pattern)
shift := make([]int, length+1)
border := make([]int, length+1)
i := length
j := length + 1
border[i] = j
for i > 0 {
for j <= length && pattern[i-1] != pattern[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 <= length; i++ {
if shift[i] == 0 {
shift[i] = j
}
if i == j {
j = border[j]
}
}
return shift
}
func Compile(pattern string) (CompiledPattern, error) {
patternSymbols, err := symbols(pattern, MaxPatternScalars, "long-pattern", "The pattern")
if err != nil {
return CompiledPattern{}, err
}
if len(patternSymbols) == 0 {
return CompiledPattern{}, &SearchError{Code: "empty-pattern", Message: "The pattern cannot be empty"}
}
return CompiledPattern{
Pattern: pattern,
Symbols: patternSymbols,
BadCharacter: buildBadCharacter(patternSymbols),
GoodSuffix: buildGoodSuffix(patternSymbols),
}, nil
}Reading the TypeScriptScalar arrays and last occurrences
The model converts strings to Unicode scalar arrays before indexing. The bad-character map keeps the last pattern position for each symbol; the good-suffix preprocessing fills a shift for each possible mismatch boundary. Its first entry is the pattern’s period, the move after a complete match, so an overlapping occurrence is never skipped.
Reading the GoRunewise parity
Go ranges over validated UTF-8 into runes, then runs the same indexed search. The structs carry the comparison trace so tests can compare the result rather than only the final hit count.
What is refusedExact input policy
Both versions accept a non-empty marker of at most 32 Unicode scalars and a document of at most 512 scalars. Matching is case-sensitive. Empty patterns, overlong input, malformed Unicode, and invalid UTF-8 in Go are rejected instead of receiving ambiguous offsets.
05 / Try a decision
How far can the marker move?
Every skip rests on one question: which alignments can this mismatch rule out? Answer it for one step of the report before you trust a jump.
Then open Try it above. No marker searches the report for escalate, which isn’t there: a no-match result still shows how many alignments
were tried and how far each one moved. Overlapping marker finds ana three times in banana and bandana, twice overlapping. After a
hit the marker moves by its period, two symbols for ana, rather than past the
whole match.
06 / Follow the cost
Pay for a marker table to skip ordinary work.
| Operation | Time | Extra space | What it assumes |
|---|---|---|---|
| Compile the marker | O(m) | O(m) | Build the last-occurrence and good-suffix tables once for a pattern of m symbols. |
| Best-case scan | O(n / m) | O(n) as shown | On text that rarely contains the marker’s letters, one right-edge comparison can skip almost a whole m-symbol window. |
| Typical text search | Often sublinear | O(n) as shown | The skip tables reduce ordinary work, especially when the alphabet is varied and the marker is not tiny. |
| Classic worst case | O(n · m) | O(n) as shown | This implementation does not add the Galil rule, so it makes no blanket linear-time promise. |
| Report z matches | O(scan + z) | O(n + z) as shown | Every hit is returned with half-open scalar offsets, including overlapping occurrences. The shown search also keeps the document as a scalar array and one trace entry per alignment. |
Let n be the document length and m the marker length, both
measured in Unicode scalars. Compilation costs O(m). The scan rows say O(n) space because the shown search keeps the document as a scalar array and
records every alignment for the film; a scan without that trace needs only the O(m) tables. The practical benefit comes from a small number of right-to-left comparisons
and shifts that jump over impossible windows.
Do not turn “often sublinear” into a guarantee. Repeated text can produce many comparisons, and this implementation does not include the Galil rule that can strengthen some worst-case bounds. Benchmark representative documents and use the platform primitive when it is faster or better maintained for the production boundary.
07 / Give it a real job
Compile the marker once, then scan a lot of text.
Command-line search is the classic home. Mike Haertel, who wrote GNU grep, explained in a 2010 mailing-list post why it is fast: “GNU grep uses the well-known Boyer-Moore algorithm, which looks first for the final letter of the target string, and uses a lookup table to tell it how far ahead it can skip in the input whenever it finds a non-matching character.”
Go’s standard library has one too. strings.NewReplacer given one old–new pair,
with an old string longer than one byte, builds a stringFinder, which its source describes as “implemented using the Boyer-Moore string search algorithm”: a badCharSkip table and a goodSuffixSkip table, built once and
reused for every string the replacer rewrites. That is this lesson’s compile and search split. Both leave out what this lesson adds for teaching: they keep no trace
and count bytes, not Unicode scalars.
This runs where a program scans a lot of text for one string: a search tool, a log pipeline,
a server that rewrites documents. In a browser, includes and indexOf are the engine’s job, so nothing in a component needs its own skip tables.
08 / Make the call
Choose the number of patterns before the skip rule.
Use Boyer–Moore when one exact marker is searched in long text. The skips grow with the marker: a longer marker over a varied alphabet can move further after each failed check. Use Rabin–Karp when a same-length fingerprint of each window is the natural question. Use Aho–Corasick when a fixed glossary of many patterns should be scanned in one pass. Use Levenshtein distance when the question is how many edits separate two strings, not where an exact copy occurs.
For a single search, short strings, or a platform with a well-tuned native search, indexOf or the standard-library equivalent is usually the clearest choice. The algorithm
earns its place when the pattern is reused, the skips matter, and the contract makes those assumptions
testable.
09 / Take the idea with you
Explain a marker search without saying “Boyer–Moore.”
“Line the word up under the text and check its last letter first. If the text’s letter there isn’t in the word at all, slide the whole word past it. If it is, slide only far enough to line up that letter. Check the letters before it only when the last one matches.”
Before moving on, load the lab’s No marker preset and predict whether the
eight-letter escalate needs more or fewer alignments than the 24 that retry takes. Then search and check.
Connections to follow nextRelated lessons
- Rabin–Karp rolling-hash search finds one exact pattern by hashing every window instead of skipping.
- Aho–Corasick scans once for a whole list of patterns.
- Hash map is the lookup behind the bad-character table when the alphabet is large.