V

Algorithm Visualizer

ZHEN
Share on WeiboShare on XGitHub repositoryAuthor website
Learning ToolsAlgorithm Complexity ReferenceAlgorithm Learning Paths
Data StructuresArrayLinked ListStackQueue and DequeBinary Search TreeBinary HeapHash TableGraphTrieDisjoint Set UnionLRU CacheSkip ListSegment TreeB+ TreeBloom FilterFenwick Tree
SortingBubble SortCocktail Shaker SortBitonic SortSelection SortInsertion SortBinary Insertion SortShell SortMerge SortTop-Down Merge SortQuick SortThree-Way Quick SortDual-Pivot Quick SortHeap SortCounting SortRadix SortBucket Sort
Graph AlgorithmsDijkstra's Shortest PathKruskal's Minimum Spanning TreePrim's Minimum Spanning TreeBellman-Ford Shortest PathsTopological SortFloyd-WarshallStrongly Connected Components2-SATMaximum FlowBipartite MatchingLowest Common AncestorEulerian Path
Dynamic ProgrammingEdit Distance0/1 KnapsackUnbounded KnapsackLongest Common SubsequenceLongest Increasing SubsequenceCoin ChangeStone MergingTraveling Salesperson DPTree Dynamic ProgrammingDigit DPRerooting DP
Backtracking and SearchN-QueensSubsetsPermutationsCombination SumMaze Solving with DFSNumber of IslandsWord SearchSudoku SolverA* Search
StringsKMP String MatchingRabin-Karp String MatchingBoyer-Moore String MatchingManacher's Longest Palindromic SubstringSuffix ArrayLCP ArrayAho-Corasick AutomatonZ Function
Math and Number TheorySieve of EratosthenesLinear SieveEuclidean AlgorithmBinary ExponentiationExtended Euclidean AlgorithmChinese Remainder TheoremEuler's Totient FunctionMiller-Rabin Primality TestFast Fourier TransformPollard's Rho Factorization
Computational GeometryConvex HullRotating CalipersClosest Pair of PointsLine Segment IntersectionBentley-Ottmann Sweep Line
SearchingBinary SearchLower and Upper BoundSearch in a Rotated Sorted ArrayBinary Search on the AnswerTernary Search

Boyer-Moore String Matching

Compare pattern characters right to left and shift by bad-character and good-suffix information after a mismatch.

Core idea

Compare the pattern from right to left. A mismatch uses knowledge of the mismatching text character, and in the full algorithm the matched suffix, to shift past alignments that cannot work.

Read the visualization

The pattern row slides beneath the text. Comparisons move left within one window, while a mismatch highlights the bad-character lookup and the resulting multi-position jump.

T
a
b
c
a
b
x
a
b
c
P
a
b
c

Align the pattern at this text window and begin comparing from its right edge.

1function boyerMoore(text: string, pat: string): number[] {
2 const n = text.length, m = pat.length;
3 const last: Record<string, number> = {};
4 for (let i = 0; i < m; i++) last[pat[i]] = i; // bad character table
5 const res: number[] = [];
6 let s = 0;
7 while (s <= n - m) {
8 let j = m - 1;
9 while (j >= 0 && pat[j] === text[s + j]) j--; // from right toward left match
10 if (j < 0) {
11 res.push(s); // all match → hit
12 s += 1;
13 } else {
14 const bc = text[s + j]; // bad character
15 s += Math.max(1, j - (last[bc] ?? -1)); // bad char step right bad char
16 }
17 }
18 return res;
19}
text Tabcabxabc
pattern Pabc
bad character tablea:0 b:1 c:2
align s0
j( from right toward left)2
searched to—
1 / 12

Complexity and tradeoffs

Time: Often sublinear; worst O(nm). Space: O(m+alphabet). Large safe shifts make it excellent in practice, while preprocessing depends on the chosen heuristics.

Invariant: Every skipped alignment is impossible under the preprocessing rule used for the mismatch.

Where it fits

Boyer-Moore is excellent for long patterns over sizable alphabets and often reads fewer text characters than the text length. Small alphabets or adversarial inputs reduce its advantage.