Abstract flowing gradient in deep indigo and blue tones, smooth and luminous, evoking a modern digital learning atmosphere

Computer Science and programming articles. We do not sell courses.

Implementing Rabin-Karp for string searching

String searching sits beneath search boxes, document pipelines, and command-line tools. A developer may first reach for Python’s in operator or str.find, but understanding an explicit pattern-matching algorithm reveals what those conveniences hide. Rabin-Karp is especially educational because it combines a rolling hash with direct comparison: it skips many possible alignments while still allowing an exact answer rather than accepting a probabilistic match. It is also a useful building block when fingerprints, cached windows, or repeated candidate generation are needed.

The Rabin-Karp algorithm compares a pattern’s hash with the hashes of successive text windows. A good implementation calculates each new window hash in constant time, verifies only promising candidates, and handles overlapping matches. That design makes the expected running time linear in the combined input sizes, although collisions can make the worst case slower. This article develops the mechanism from first principles, then provides Python code, complexity analysis, and practical tests for the edge cases that commonly appear in real text.

How rolling hashes locate patterns

Suppose a text has length (n) and a pattern has length (m). Treat each character as a numeric code and interpret a string (s) as a polynomial whose coefficients are those codes. For a base (b) and prime modulus (q), its hash is:

[ H(s) = \left(\text{code}(s[0])b^{m-1} + \cdots + \text{code}(s[m-1])\right) \bmod q ]

Python’s ord supplies the codes, so the same approach works with Unicode rather than only ASCII. The modulus keeps each intermediate value bounded, while the base determines how positions contribute to the result.

The crucial optimisation is that adjacent windows overlap. If the current window begins at (i), subtract the contribution of text[i], multiply the remaining value by (b), and append the code of text[i+m]. The next hash is:

[ \left((H-\text{code}(text[i])b^{m-1})b+\text{code}(text[i+m])\right)\bmod q ]

The required power is calculated once. Moving from one window to the next therefore takes (O(1)) hash work, regardless of pattern length, and the scanner can test every possible alignment without rebuilding the polynomial.

Equal hashes are not proof of equality. Two different strings can produce the same residue, just as two different Australian phone prefixes can share a shortened advertising number. A reliable matcher therefore treats hash equality as a candidate event and compares the actual substrings before recording a result. This verification preserves correctness; collisions affect speed rather than output. A system that accepts hash equality without verification becomes a probabilistic filter with a tunable false-positive rate and should not be described as an exact string search.

Choosing safe hash parameters

The modulus (q) should be large enough that accidental collisions are rare. A prime near one billion works well for many educational and internal tools, and Python’s arbitrary-precision integers make overflow a non-issue. The base must be greater than the character-code range if the polynomial is intended to encode distinct digit sequences cleanly. For Unicode code points, a base above 1,114,111 is appropriate; for ASCII-only data, 256 is conventional. Larger alphabets increase intermediate multiplication costs but not the number of window updates.

A fixed pair of parameters is easy to reproduce but can be vulnerable to deliberately constructed collisions. If patterns arrive from untrusted users and the hash is used as a prefilter, choose the base at process start from a cryptographically strong random source. Two independent hashes can also reduce false candidates, at the cost of extra arithmetic and storage. Double hashing is rarely necessary when every candidate is verified exactly, but it can be worthwhile when verification dominates the workload.

Hashing also has a looser relationship to machine learning than the shared word “hash” might suggest. The text classification guide explains how documents become numerical features for a Naive Bayes classifier; that feature encoding differs from Rabin-Karp’s rolling polynomial. The useful lesson is the separation of responsibilities: convert symbols into stable numeric representations, apply a suitable hash, and retain any exact comparison required by the application’s correctness contract.

Building a Python implementation

The following function returns the start index of every occurrence, including overlaps. It searches by Unicode character index, rejects an empty pattern, and returns an empty list when the pattern is longer than the text. The code targets Python 3.9 or later because it uses the built-in list[int] annotation.

def rabin_karp(text: str, pattern: str) -> list[int]:
    if not pattern:
        raise ValueError("pattern must not be empty")

    n, m = len(text), len(pattern)
    if m > n:
        return []

    modulus = 1_000_000_007
    base = 1_114_112

    pattern_hash = 0
    for i in range(m):
        pattern_hash = (
            pattern_hash * base + ord(pattern[i])
        ) % modulus

    window_hash = 0
    for i in range(m):
        window_hash = (
            window_hash * base + ord(text[i])
        ) % modulus

    highest_power = pow(base, m - 1, modulus)
    matches = []

    for start in range(n - m + 1):
        if (
            window_hash == pattern_hash
            and text[start:start + m] == pattern
        ):
            matches.append(start)

        if start + m < n:
            outgoing = ord(text[start])
            incoming = ord(text[start + m])
            window_hash = (
                (window_hash - outgoing * highest_power) * base + incoming
            ) % modulus

    return matches

Before scanning, the function computes the pattern hash and the first window hash. It also stores highest_power, which equals (b^{m-1}) modulo (q). During the scan, the rolling formula updates the window hash. When that hash equals the pattern hash, a direct slice comparison confirms the candidate. This second check makes the implementation exact even if unrelated strings collide. Every confirmed start is appended, so overlapping occurrences are preserved without special-case logic.

The algorithm uses (O(m)) work to hash the pattern and (O(1)) work for each window transition, giving (O(n+m)) time when collisions and successful-match checks are negligible. Exact verification adds (O(m)) for each true match and false collision; with (k) matches, that additional work is (O((k+c)m)), where (c) is the number of collisions. The scanner keeps only fixed hash state, although the returned list occupies (O(k)) space and temporary substring slices can allocate (O(m)) memory.

Verifying correctness and edge cases

Useful tests cover empty input, a pattern longer than the text, a match at either boundary, repeated characters, and overlapping occurrences. Searching aaaaa for aaa should produce indices 0, 1, and 2, while searching short for longer should produce no indices. Case sensitivity should be explicit: searching arvo finds lowercase text but not Arvo. Include non-ASCII samples as well, such as finding ïve in naïve, to confirm that code points and index positions behave as intended.

Case-insensitive search requires a defined normalisation policy. Lowercasing both strings is simple for most English text, but some Unicode transformations can change length or context. A full case fold may expand one code point into several, invalidating offsets calculated in the original string. If exact source positions matter, normalise one character at a time while retaining an index map, or document that the function returns positions in the normalised text. Australian documents may contain names, official place names, and program names whose capitalisation must remain significant.

Correctness testing should not depend on luck with collisions. One approach is to compare the matcher with Python’s text.find on many random patterns, checking every returned index and searching until find fails to uncover later occurrences. A separate benchmark should then measure long adversarial strings and realistic inputs. KMP is a useful deterministic alternative when guaranteed (O(n+m)) behaviour matters; Rabin-Karp is most compelling when an implementation needs explicit rolling fingerprints or a custom multi-stage search process.

Real projects and reliable recommendations

Australian teams encounter the algorithm in small but varied data-cleaning jobs. A Canberra transport team might search ACT open-data exports for route or stop names; records around Sydney and Melbourne commonly mix forms such as Rd, St, and Cres with full street names. Search tools for community groups may contain informal spellings such as arvo, an Australian word for the afternoon, alongside formal titles. Consumer-facing datasets may also contain +61 numbers, 1300 service numbers, and mobile prefixes beginning 04, so field-aware matching can be more useful than one undifferentiated query.

For repeated searches over indexed documents, preprocessing can keep each query responsive. The segment tree guide explains how block summaries support range queries; a Rabin-Karp fingerprint for each block can serve as another prefilter before finer candidate checks. This is not a substitute for a suffix index in a large static corpus, and building the structure costs time and memory, but it fits internal tools where data changes in batches. For ordinary single-pattern work, Python’s built-in search remains the simplest choice.

A dependable implementation usually follows a short set of engineering checks:

Method Best suited to Time profile Main trade-off
Built-in in or find Routine one-pattern lookup Implementation-dependent Simple, but the algorithm is hidden
Naive comparison Teaching and tiny inputs (O(nm)) worst case Repeats many character comparisons
KMP Deterministic single-pattern search (O(n+m)) Requires a prefix table
Rabin-Karp Rolling fingerprints and candidate filtering (O(n+m)) scan; (O(nm)) worst case Needs collision handling and exact verification