Published by Dimitris Kougioumtzis · Updated
Compare right to left and combine bad-character and strong good-suffix shifts. This first-match version does not use the Galil rule.
Compare pattern characters from right to left. At a mismatch, compute both the bad-character displacement and the strong good-suffix displacement, then advance by their maximum.
When to use Boyer-Moore string matching
Finding the first exact occurrence of a fixed pattern in a longer text.
Choosing an alternative
Horspool uses a simpler single-character shift table. This view computes the full good-suffix table as well.
Worked example: input and state changes
Example input
ABAAABCDABC | ABC
These checkpoints follow the actual example timeline. State details show the stored values and decisions; use the visualization to inspect every intervening step.
Step 0: Text, aligned pattern, and good-suffix shifts before preprocessing.
State at this checkpoint
{ "values": [ "A", "B", "A", "A", "A", "B", "C", "D", "A", "B", "C", "A", "B", "C", "", "", "", "", "", "", "", "", 0, 0, 0, 0, "", "", "", "", "", "", "" ], "active": [], "kind": "matrix", "columns": 11, "goodSuffix": [ 3, 3, 3, 1 ], "result": -1 }Step 2: Mismatch: bad-character shift 2, good-suffix shift 1; advance 2.
State at this checkpoint
{ "values": [ "A", "B", "A", "A", "A", "B", "C", "D", "A", "B", "C", "A", "B", "C", "", "", "", "", "", "", "", "", 3, 3, 3, 1, "", "", "", "", "", "", "" ], "active": [ 2, 13 ], "kind": "matrix", "columns": 11, "goodSuffix": [ 3, 3, 3, 1 ], "result": -1 }Step 5: Shift the pattern.
State at this checkpoint
{ "values": [ "A", "B", "A", "A", "A", "B", "C", "D", "A", "B", "C", "", "", "", "", "A", "B", "C", "", "", "", "", 3, 3, 3, 1, "", "", "", "", "", "", "" ], "active": [], "kind": "matrix", "columns": 11, "goodSuffix": [ 3, 3, 3, 1 ], "result": -1 }Step 7: Matching characters; compare from right to left.
State at this checkpoint
{ "values": [ "A", "B", "A", "A", "A", "B", "C", "D", "A", "B", "C", "", "", "", "", "A", "B", "C", "", "", "", "", 3, 3, 3, 1, "", "", "", "", "", "", "" ], "active": [ 5, 16 ], "kind": "matrix", "columns": 11, "goodSuffix": [ 3, 3, 3, 1 ], "result": -1 }Step 9: First match starts at index 4.
State at this checkpoint
{ "values": [ "A", "B", "A", "A", "A", "B", "C", "D", "A", "B", "C", "", "", "", "", "A", "B", "C", "", "", "", "", 3, 3, 3, 1, "", "", "", "", "", "", "" ], "active": [], "kind": "matrix", "columns": 11, "goodSuffix": [ 3, 3, 3, 1 ], "result": 4 }
Expected final state
First match starts at index 4.
Complexity and input bounds
Family: Strings. Time complexity: O(nm) worst case; O(n/m) best case.
Implementation detail: Three matrix rows show text, aligned pattern, and good-suffix shifts. UI inputs are bounded ASCII letters. Downloads use ASCII integer codes, allow an empty pattern, and return the first index or -1.
Space complexity: O(m + alphabet size) auxiliary storage, plus recorded frames.
Working-space bounds describe algorithm state and any explicitly noted output, excluding the visualization's saved timeline. Recording frames can use more memory than running the function alone. Here n is sequence length, V and E are vertex and edge counts, and other parameters refer to the named input dimensions.
ASCII letters: text 1..32 | pattern 1..12. Case-sensitive.
The playground validates these limits before starting. Downloaded functions are callable implementations, with parameter and output-buffer contracts in their comments; they do not all repeat the playground's input validation.
Common mistakes and limitations
The strong good-suffix table has m+1 entries. Preprocessing must handle repeated borders. This first-match implementation does not include the Galil rule, so its stated worst-case bound is O(nm).
Further reading
For background on algorithm analysis and the JavaScript function interface:
- MIT OpenCourseWare: algorithm design and analysis foundations
- MDN: JavaScript function parameters and return values
Editorial and testing approach · Browse all algorithm guides
Complete JavaScript implementation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | // First occurrence or -1; empty pattern returns 0. n 0..32, m 0..12, text/pattern ASCII letter codes. Both bad-character and strong good-suffix preprocessing; no Galil rule. O(nm) worst case, O(m+256) auxiliary space. Reference snippets assume validated playground inputs. Fixed scratch buffers have 256 slots. Sorting variants may use a different traversal strategy than the animation. function algorithm(text, n, pattern, m) { if (m == 0) { return 0; } let last = Array(256).fill(0); let shift = Array(256).fill(0); let border = Array(256).fill(0); let i = m; let j = m + 1; let position = 0; let advance = 0; for (let c = 0; c < 256; c++) { last[c] = -1; } border[i] = j; while (i > 0) { while (j <= m && 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 <= m; i++) { if (shift[i] == 0) { shift[i] = j; } if (i == j) { j = border[j]; } } for (i = 0; i < m; i++) { last[pattern[i]] = i; } while (position <= n-m) { j = m-1; while (j >= 0 && pattern[j] == text[position+j]) { j--; } if (j < 0) { return position; } advance = j-last[text[position+j]]; if (shift[j+1] > advance) { advance = shift[j+1]; } position += advance; } return -1; } |
Source
Primary research for the matching method. The playground uses bounded ASCII inputs and standalone teaching implementations rather than the original publication program.
- A fast string searching algorithm
Robert S. Boyer; J Strother Moore (1977). Original research paper.