Boyer-Moore Good-Suffix Preprocessing

Why Right-to-Left Matching Helps

At alignment $s$, Boyer–Moore compares $P[0\dots m)$ with $T[s\dots s+m)$ from right to left. A left-to-right mismatch usually rejects only the current start. A right-to-left mismatch may first prove that a long suffix matches, enabling both a bad-character shift and a good-suffix shift.

If the mismatch is at pattern index $j$, the suffix $P[j+1\dots m)$ has already matched. Any nearby valid alignment must place compatible pattern content over that text suffix. The bad-character rule uses the mismatching text symbol; the good-suffix rule uses the matched suffix. Search advances by the maximum positive safe shift.

Strong Good-Suffix Cases

After a mismatch at $j$, let $G=P[j+1\dots m)$. In the first case, $G$ occurs earlier in the pattern. The strong rule chooses the rightmost earlier occurrence not preceded by the mismatching symbol $P[j]$; otherwise the shift would reproduce the known mismatch immediately.

If no compatible internal occurrence exists, align the longest suffix of $G$ that is also a prefix of $P$. This matched-prefix fallback preserves the only remaining overlap that could lead to a match. If no non-empty prefix qualifies, move beyond the matched suffix. After a full match, the same prefix structure aligns the pattern's longest proper border and preserves overlapping occurrences.

Building the Shift Tables

Strong preprocessing scans right to left. border_position[i] links the suffix beginning at $i$ to its next border candidate. When the characters preceding two candidate suffixes differ, the current suffix occurrence is compatible with the mismatch; record its displacement if that shift entry is still empty. Following border links tests progressively shorter suffixes.

The first pass fills internal-occurrence shifts. A second walk over the full pattern's border chain fills remaining entries with matched-prefix fallbacks. The table has length $m+1$: search uses shift[j + 1] after a mismatch at $j$ and shift[0] after a complete match.

def strong_good_suffix_shifts(pattern: str) -> list[int]:
    """Build shifts; shift[j+1] handles mismatch j, shift[0] a match."""
    m = len(pattern)
    if m == 0:
        return [1]

    shift = [0] * (m + 1)
    border_position = [0] * (m + 1)
    i, j = m, m + 1
    border_position[i] = j

    while i > 0:
        while j <= m and pattern[i - 1] != pattern[j - 1]:
            if shift[j] == 0:
                shift[j] = j - i
            j = border_position[j]
        i -= 1
        j -= 1
        border_position[i] = j

    j = border_position[0]
    for i in range(m + 1):
        if shift[i] == 0:
            shift[i] = j
        if i == j:
            j = border_position[j]
    return shift


def boyer_moore_search(text: str, pattern: str) -> list[int]:
    """Combine strong good-suffix and bad-character shifts."""
    if pattern == "":
        return list(range(len(text) + 1))
    n, m = len(text), len(pattern)
    if m > n:
        return []

    good = strong_good_suffix_shifts(pattern)
    last = {symbol: index for index, symbol in enumerate(pattern)}
    result: list[int] = []
    alignment = 0

    while alignment <= n - m:
        j = m - 1
        while j >= 0 and pattern[j] == text[alignment + j]:
            j -= 1
        if j < 0:
            result.append(alignment)
            alignment += max(1, good[0])
        else:
            bad = j - last.get(text[alignment + j], -1)
            alignment += max(1, bad, good[j + 1])
    return result


def naive_search(text: str, pattern: str) -> list[int]:
    if pattern == "":
        return list(range(len(text) + 1))
    return [
        i for i in range(len(text) - len(pattern) + 1)
        if text[i:i + len(pattern)] == pattern
    ]


if __name__ == "__main__":
    cases = [
        ("ZZCDABCDAB", "ABCDAB"),
        ("aaaaa", "aaa"),
        ("banana", "ana"),
        ("abc", ""),
        ("mississippi", "issi"),
        ("abababab", "abab"),
        ("short", "a-much-longer-pattern"),
    ]
    for text, pattern in cases:
        expected = naive_search(text, pattern)
        actual = boyer_moore_search(text, pattern)
        assert actual == expected, (text, pattern, expected, actual)
        print(pattern, text, actual)

Combining Heuristics and Guarantees

At mismatch $j$, the bad-character rule aligns the mismatching text symbol with its rightmost occurrence at or before $j$, or moves past it if absent. The good-suffix rule preserves the already matched suffix. Since each independently excludes smaller unsafe alignments, their maximum positive shift is safe.

Basic Boyer–Moore has excellent average behavior but can make $O(nm)$ comparisons on repetitive inputs. The Galil rule remembers regions already proved equal and supports linear worst-case searching with the full construction. Horspool uses the character aligned with the final pattern position, while Sunday uses the character immediately after the window; both simplify preprocessing but retain quadratic worst cases.