String Matching, in depth: choosing between naive, Horspool, Rabin-Karp and Two-Way, worst cases and Unicode traps

Choosing a matcher in one picture

The model: alignments, verification and shifts

Fix the vocabulary first. The text has length n, the pattern has length m, and the alphabet has size sigma. An alignment is a position i where the pattern is laid against text[i:i+m]. Every exact matcher does two things: it verifies alignments, and it decides how far to move after one fails. The algorithms differ only in how much they learn from a failed verification and how cheaply they learn it.

The naive matcher learns nothing. It tries every alignment and compares left to right until a mismatch, so its cost is the sum of the comparison lengths. On random text over a large alphabet most alignments fail on the first or second character, giving roughly n comparisons, which is why naive search is fast in practice. On text aaaa...a with pattern aaa...ab every alignment runs m comparisons before failing, and the cost becomes n times m. Every worst case on this page has that shape: periodic text and a pattern that almost matches everywhere.

The naive loop is still a strong baseline, because libraries use vector instructions to scan 16 or 32 bytes per step for the pattern's first byte and verify only at candidates. For short patterns over natural text that is very hard to beat, and any clever algorithm has to win against it on your data.

Horspool: skipping with the bad-character rule

Boyer-Moore's insight is to compare the alignment from right to left. If the last character of the window does not even occur in the pattern, no alignment that covers that character can match, so the pattern can jump a full m positions. Horspool's simplification keeps only this bad-character rule and always keys the shift on the text character under the last pattern position, which removes Boyer-Moore's more complex good-suffix table while keeping most of its speed on natural text.

The shift table records, for each character, the distance from its last occurrence in the pattern (excluding the final position) to the end. Characters that do not occur shift by m.

def horspool(text, pat):
    """Index of the first occurrence of pat in text, or -1. Matches str.find."""
    m, n = len(pat), len(text)
    if m == 0:
        return 0
    shift = {}
    for i in range(m - 1):              # last position excluded on purpose
        shift[pat[i]] = m - 1 - i
    i = 0
    while i <= n - m:
        j = m - 1
        while j >= 0 and text[i + j] == pat[j]:
            j -= 1
        if j < 0:
            return i
        i += shift.get(text[i + m - 1], m)
    return -1

Excluding the last pattern position matters. If it were included, the final character would get a shift of zero and the loop would never advance after a mismatch whose window ends in that character. The dictionary keeps the table sparse, so the code works for bytes and Unicode alike.

The worst case is easy to provoke. Search "a" * n for "b" + "a" * (m - 1): the last character always matches, the right-to-left scan walks back m - 1 characters before failing on the b, and the shift for a is 1. That is n times m comparisons, exactly as bad as naive search, and an attacker who controls the text can construct it for any pattern they can see.

Worked example: a Horspool trace

Search HERE IS A SIMPLE EXAMPLE (24 characters) for EXAMPLE (m = 7). The shift table over the first six pattern characters is E 6, X 5, A 4, M 3, P 2, L 1; every other character shifts 7.

Five alignments and 15 character comparisons find the match at index 17. The naive loop would try 18 alignments. Notice that the shift at alignment 9 is keyed on the last window character E, not on the I that caused the mismatch; that is the Horspool simplification, and it is why the code needs only one table.

Rabin-Karp and why the base must be random

Rabin-Karp takes a different route. It treats each window as a number, a polynomial in some base b reduced modulo a large prime p, and slides the window by subtracting the outgoing character and adding the incoming one in constant time. Only windows whose hash equals the pattern's hash are verified. Its value is flexibility rather than single-pattern speed: one rolling hash checks many same-length patterns at once and finds repeated substrings.

import random

MOD = (1 << 61) - 1          # a Mersenne prime; Python ints never overflow

def rabin_karp(text: bytes, pat: bytes) -> list[int]:
    """Every start index of pat in text. Verifies each hash hit, so never wrong."""
    n, m = len(text), len(pat)
    if not 0 < m <= n:
        return []
    b = random.randrange(256, MOD - 1)        # secret, per-call base
    hp = ht = 0
    for i in range(m):
        hp = (hp * b + pat[i]) % MOD
        ht = (ht * b + text[i]) % MOD
    top = pow(b, m - 1, MOD)                  # weight of the outgoing byte
    out = []
    for i in range(n - m + 1):
        if ht == hp and text[i:i + m] == pat:
            out.append(i)
        if i + m < n:
            ht = ((ht - text[i] * top) * b + text[i + m]) % MOD
    return out

The random base is the security feature. With a fixed, published base an attacker can craft text full of windows that collide with your pattern's hash, and every collision costs an m-byte verification, which returns you to n times m. With b drawn at random after the inputs are fixed, two different strings of length m collide with probability at most (m - 1) / p, because their difference is a nonzero polynomial of degree below m with at most m - 1 roots. With p near 2 to the 61st power that is negligible even for megabyte patterns. Skipping verification turns it into a Monte Carlo algorithm that can report false matches.

Two-Way: linear worst case without a table

Engineers want two things at once: Horspool-like speed on ordinary text and a linear bound on hostile text, without KMP's m-entry table. Crochemore and Perrin's Two-Way algorithm delivers both. It splits the pattern at a critical factorisation into a left part u and a right part v, chosen using the pattern's maximal suffixes so that the split respects the pattern's period. At each alignment it compares v left to right; a mismatch there allows a shift proportional to how far it got. If v matches, it compares u right to left; a mismatch there allows a shift by the period. Because of the way the split is chosen, no text character is compared more than a constant number of times, so the search is O(n + m) time with O(1) extra space.

This is not a curiosity. CPython adopted an enhanced Two-Way implementation in Python 3.10 (bpo-41972) for forward searches such as find, index, in, replace and partition, replacing quadratic worst cases that the previous Horspool-style loop allowed; reverse searches like rfind were not changed. CPython still chooses between strategies based on needle and haystack sizes, and the exact thresholds have changed between releases, so read Objects/stringlib/fastsearch.h and the accompanying stringlib_find_two_way_notes.txt for the version you run rather than relying on a number from a blog post. The notes file is the best starting point if you must implement Two-Way yourself.

So in Python a hand-written matcher almost certainly loses to str.find; write one only for a capability the built-in lacks.

Comparison and where the other tools fit

When you need many patterns, build an automaton over a trie (Aho-Corasick) rather than looping a single-pattern matcher. When you need many queries against one fixed text, invert the problem and index the text with a suffix array and its LCP array, so each query costs O(m log n) or better regardless of n. When the pattern contains wildcards, matching can be expressed as a sum of convolutions and computed with the fast Fourier transform. When the pattern has alternation or repetition, you need a regular-expression engine; the regex article explains why automaton-based engines are the safe choice there.

Unicode: when the right algorithm gives the wrong answer

Most string-matching bugs in production are not algorithm bugs. They are disagreements about what a character is.

• Normalisation. The letter e-acute can be one code point (U+00E9) or two (e followed by U+0301 combining acute accent). They render identically and compare unequal: "e\u0301" == "\u00e9" is False. Normalise both text and pattern to the same form (NFC is the usual choice) before matching, or a search for a name will miss half the records that contain it.
• Case folding changes lengths. "Straße".casefold() is "strasse", seven characters from six. If you fold the text, match and then report the index, the index points into the folded copy, not the original. Keep an offset map from folded positions back to source positions, or match on the original with a case-insensitive comparison that understands the folding. Use casefold, not lower, for caseless matching.
• Bytes versus code points versus graphemes. UTF-8 is self-synchronising, so a byte-level match never starts mid-character, but it can split a grapheme cluster, such as a base letter whose accent follows as a separate code point. If users mean graphemes, check boundaries after matching.

Failure modes

• Quadratic search on hostile input. A log scanner using a naive or Horspool loop over attacker-supplied text can be driven to n times m work per rule. Use a linear-time matcher (Two-Way, KMP or an automaton) anywhere an attacker chooses the text.
• Fixed hash bases. Rabin-Karp or any rolling-hash index with a constant base is a collision target. Draw the base at random per process or per call, and always verify hits.
• Off-by-one in the shift table. Including the last pattern character in Horspool's table produces a zero shift and an infinite loop. Test against a brute-force oracle with small alphabets, where repeated characters exercise the edge cases.
• Overlapping versus non-overlapping matches. Searching aaaa for aa yields three overlapping matches or two non-overlapping ones. str.count returns the non-overlapping count. Decide which your caller needs and test it explicitly.
• Chunk boundaries in streams. A match straddling two reads is missed if chunks are searched independently; carry matcher state across chunks or overlap buffers by m - 1 bytes.
• Benchmarking on the wrong data. Random bytes flatter Horspool; DNA, base64 and log lines do not. Benchmark on the real corpus and a constructed worst case.

What to do next

1. Write down the four facts that decide the choice for your workload: pattern length distribution, effective alphabet, whether input streams, and whether anyone untrusted chooses text or pattern.
2. Start with your language's built-in search and measure it on a real corpus sample before writing anything. Replace it only for a capability it lacks.
3. If you implement Horspool or Rabin-Karp, port the code above and run it against a brute-force oracle on thousands of random strings over two-, four- and eight-letter alphabets, including empty and length-one patterns.
4. Build an adversarial benchmark: periodic text against an almost-matching pattern. Any matcher that goes quadratic on it must not see untrusted input.
5. Normalise text and patterns to one Unicode form and fold case with casefold; if you report positions, keep a map back to the original offsets.
6. For many patterns, move to Aho-Corasick; for many queries over one text, build a suffix array; for wildcards or alternation, use an automaton-based regex engine.