Sublinear Average-Case Matching: Boyer-Moore Bad-Character/Good-Suffix & Horspool

1. Right-to-Left Comparison & The Two Shift Rules

Suppose pattern $P[0..M-1]$ is aligned at text offset $s$, so $P[j]$ sits above $T[s + j]$. We compare from $j = M - 1$ down to $0$. When a mismatch occurs at pattern index $j$ ($P[j] \neq T[s + j]$), we have already verified that the suffix $P[j+1..M-1]$ matches $T[s+j+1..s+M-1]$. Boyer-Moore takes the maximum shift proposed by two independent rules:

• Bad-Character Rule: Let $c = T[s + j]$ be the mismatched text byte, and let $\text{last}[c]$ be the rightmost index in $P[0..M-2]$ where byte $c$ appears ($-1$ if absent). To align $T[s + j]$ with that occurrence in $P$, we shift the window right by $\Delta_{\text{bad}} = \max(1,\; j - \text{last}[c])$. If $c$ does not appear in $P$ at all, $\Delta_{\text{bad}} = j - (-1) = j + 1$; when the mismatch happens immediately at $j = M - 1$, the window leaps by a full $M$ bytes!
• Good-Suffix Rule: Let $t = P[j+1..M-1]$ be the matched suffix before the mismatch. We shift $P$ right to align $T[s+j+1..s+M-1]$ with the rightmost earlier occurrence of $t$ in $P$ that is not preceded by the same mismatched character $P[j]$ (the strong good-suffix rule), or, if no full copy of $t$ exists inside $P$, with the longest prefix of $P$ that matches a suffix of $t$.

Combined with the Galil rule (which remembers matched prefixes across shifts so characters are never re-compared), full Boyer-Moore runs in $O(N + M)$ worst-case time (at most $3N$ comparisons on non-periodic patterns) and $O(N / M)$ average time.

2. Boyer-Moore-Horspool (BMH): Simplifying the Inner Loop

Nigel Horspool observed in 1980 that on natural alphabets ($|\Sigma| = 256$), the Bad-Character shift dominates the Good-Suffix shift almost everywhere, while computing and branching on two tables slows down the CPU pipeline. Horspool's algorithm always computes the shift using the text byte aligned with the last position of the pattern, $c_{\text{end}} = T[s + M - 1]$, regardless of where the mismatch occurred inside the window:

Note that $P[M - 1]$ itself is deliberately excluded when building $\text{shift}[c]$ so that $\text{shift}[c] \ge 1$ is strictly guaranteed, preventing zero-length infinite loops.

3. Visual Trace: BMH Shift Table & Window Leaps

Below we search for $P = \texttt{"NEEDLE"}$ ($M = 6$). Notice that $P[0..4] = \texttt{"NEEDL"}$ has rightmost indices $\text{last}[\texttt{'N'}] = 0$, $\text{last}[\texttt{'E'}] = 2$, $\text{last}[\texttt{'D'}] = 3$, $\text{last}[\texttt{'L'}] = 4$, giving shifts $M - 1 - \text{last}[c]$: $\text{shift}[\texttt{'N'}] = 5$, $\text{shift}[\texttt{'E'}] = 3$, $\text{shift}[\texttt{'D'}] = 2$, $\text{shift}[\texttt{'L'}] = 1$, and $\text{shift}[\text{other}] = 6$ (including $\texttt{'E'}$ at $P[5]$ being ignored so $\text{shift}[\texttt{'E'}] = 3$, not $0$).

4. Production Implementation: BMH with Rare-Byte Guard

#include <array>
#include <cstdint>
#include <cstring>
#include <string_view>
#include <vector>

// Boyer-Moore-Horspool with First+Last Character Guard before memcmp
std::vector<size_t> bmh_search(std::string_view text, std::string_view pat) {
    std::vector<size_t> matches;
    const size_t n = text.size(), m = pat.size();
    if (m == 0 || n < m) return matches;

    // 1. Precompute 256-entry Bad-Character shift table for pat[0 .. m-2]
    std::array<size_t, 256> shift;
    shift.fill(m);
    for (size_t k = 0; k + 1 < m; ++k) {
        shift[static_cast<uint8_t>(pat[k])] = m - 1 - k;
    }

    const uint8_t last_byte = static_cast<uint8_t>(pat[m - 1]);
    const uint8_t first_byte = static_cast<uint8_t>(pat[0]);

    // 2. Scan alignment windows with sublinear skips
    size_t s = 0;
    while (s <= n - m) {
        const uint8_t c_end = static_cast<uint8_t>(text[s + m - 1]);
        if (c_end == last_byte && static_cast<uint8_t>(text[s]) == first_byte) {
            if (m <= 2 || std::memcmp(text.data() + s + 1, pat.data() + 1, m - 2) == 0) {
                matches.push_back(s);
            }
        }
        s += shift[c_end];
    }
    return matches;
}