CoreSource checked

Horspool Algorithm

Finds exact string matches by shifting with the bad-character rule from the pattern's last position.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Pattern Matching
Difficulty: Intermediate
Family: String Matching
Tier: Core
Status: Verified
Review: Source Checked
Sources: 3
Formulas: 0
Relationships: 3
Code example: Ready
Visualization: Ready

Overview

Horspool's algorithm compares the pattern against a text window and, after a mismatch, shifts the window using the text character aligned with the pattern's last character.

Core Concepts

exact string matchingstring matchingmatchingpattern matching

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(n)

Average

O(n + m)

Worst

O(n + m)

Space

O(n + m)

When to Use

Use for exact single-pattern search when a compact bad-character table is enough.
Use when average-case speed matters more than a stronger worst-case guarantee.

When Not to Use

Avoid when streaming input prevents random access to the current window.
Avoid when many patterns must be searched at once; multi-pattern automata are a better fit.

What It Does

Horspool Algorithm uses shifting by the last character aligned under the pattern for exact string matching
Organizes the work around exact string matching and string matching.

Use Cases

Production and research workloads requiring string matching via Finds exact string matches by shifting with the bad-character rule from the pattern's last position.
String Matching pipelines where O(n + m) time and O(n + m) space fit system constraints.
Engineering comparisons against Bit-Parallel Levenshtein and Shift-And Algorithm when tuning string matching.

Inputs

Text or sequence
Pattern, index, or comparison sequence

Outputs

Matches, alignment, index, or similarity value

Pseudocode

1.Build the Horspool shift table from the pattern
2.Set window start i = 0
3.While the pattern fits in the text
4.Compare pattern characters from right to left
5.If all characters match, report i
6.Otherwise shift by table[text[i + pattern.length - 1]]

Canonical Example

Input: pattern 'needle', text 'findaneedle'
Output: match at index 5
Explanation: Failed windows shift according to the character aligned with the last pattern position until the full pattern matches.

Implementation Notes

Initialize missing characters to shift by the full pattern length.
Fill shifts from the rightmost occurrence before the last pattern character.
Compare windows right-to-left so mismatches near the end fail quickly.

Common Pitfalls

The shift table is based on pattern characters before the last position.
Mismatches still shift by the character under the pattern's last character, not necessarily the mismatched character.
Short patterns and repeated characters need explicit tests.