Published by Dimitris Kougioumtzis · Updated
Search with a right-to-left comparison and a bad-character shift table.
Compare from the pattern's right edge, then use a precomputed character shift to skip safe window positions.
When to use Boyer–Moore–Horspool search
Exploring skip-based string matching.
Choosing an alternative
KMP uses prefix structure instead of character-based shifts.
Worked example: input and state changes
Example input
ABABABCABAB | ABABC
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: Initial state.
State at this checkpoint
{ "values": [ "A", "B", "A", "B", "A", "B", "C", "A", "B", "A", "B" ], "active": [] }Step 2: Shift by 2 from character A.
State at this checkpoint
{ "values": [ "A", "B", "A", "B", "A", "B", "C", "A", "B", "A", "B" ], "active": [ 4 ] }Step 5: Compare backward at text index 4.
State at this checkpoint
{ "values": [ "A", "B", "A", "B", "A", "B", "C", "A", "B", "A", "B" ], "active": [ 4 ] }Step 7: Compare backward at text index 2.
State at this checkpoint
{ "values": [ "A", "B", "A", "B", "A", "B", "C", "A", "B", "A", "B" ], "active": [ 2 ] }Step 9: Matches at indices: 2.
State at this checkpoint
{ "values": [ "A", "B", "A", "B", "A", "B", "C", "A", "B", "A", "B" ], "active": [] }
Expected final state
Matches at indices: 2.
Complexity and input bounds
Family: Strings. Time complexity: O(nm) worst.
Space complexity: O(alphabet size) shift table.
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.
Text | pattern. Use 1–40 letters for text and 1–16 for pattern.
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
Large average skips do not establish a linear worst-case bound; initialize default shifts correctly.
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 | // ASCII letter-code arrays, n ≤ 40, 1 ≤ m ≤ 16. Writes all overlapping match indices and returns count. 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, matches) { let shift = Array(256).fill(0); for (let i = 0; i < 128; i++) { shift[i] = m; } for (let i = 0; i < m - 1; i++) { shift[pattern[i]] = m - 1 - i; } let end = m - 1; let count = 0; while (end < n) { let j = m - 1; while (j >= 0 && text[end - m + 1 + j] == pattern[j]) { j--; } if (j < 0) { matches[count++] = end - m + 1; } end += shift[text[end]]; } return count; } |
Source
Primary research source for the algorithm or its underlying method. The playground is a bounded teaching implementation, not the publication's original program.
- Practical fast searching in strings
R. Nigel Horspool (1980). Research paper.