Rabin-Karp Algorithm

The Rabin-Karp algorithm is a string matching algorithm that uses hashing to find patterns in text. It uses a rolling hash to efficiently compute hash values for all substrings of the text.

Algorithm

The algorithm computes the hash value of the pattern and compares it with hash values of all substrings of the text. When hash values match, it performs a character-by-character comparison to confirm the match (hashes can collide, so a match is a strong hint, not proof). Comparing two hashes costs $O(1)$ where comparing two strings costs $O(m)$ — that is the entire speedup.

Why rolling specifically? Hashing each window from scratch costs $O(m)$ per position — $O(nm)$ total, no better than naive scanning. The rolling hash instead updates the previous window's value in $O(1)$: subtract the contribution of the character leaving the window, shift, add the character entering. All $n$ windows together then cost $O(n)$.

Where it is used in practice: searching for many patterns at once (hash them all into a set and roll a single pass over the text — plagiarism and duplicate-content detection work this way), content-defined chunking in sync and backup tools of the rsync family (the rolling hash decides chunk boundaries), and substring matching in genomics, where the text is long and the alphabet small.

Time Complexity

The average time complexity is $O(n+m)$, where $n$ is the length of the text and $m$ is the length of the pattern. The worst case is $O(nm)$ when many hash collisions occur.

Implementation

def rabin_karp_search(text, pattern):
    """Perform Rabin-Karp search for the pattern in the text."""
    # Parameters
    d = 256  # Number of characters in the input alphabet (assuming ASCII)
    q = 101  # A prime number for hashing

    # Lengths of pattern and text
    m = len(pattern)
    n = len(text)

    # Calculate the hash value of the pattern and the first window of text
    p_hash = 0
    t_hash = 0
    h = 1

    # Calculate the value of h = d^(m-1) % q
    for i in range(m - 1):
        h = (h * d) % q

    # Calculate the hash value of the pattern and the first window of text
    for i in range(m):
        p_hash = (d * p_hash + ord(pattern[i])) % q
        t_hash = (d * t_hash + ord(text[i])) % q

    # Search for the pattern
    for i in range(n - m + 1):
        # Check if the hash values match
        if p_hash == t_hash:
            # If hash values match, check for actual substring match
            if text[i:i + m] == pattern:
                print("Pattern found at index {}".format(i))

        # Calculate hash value for the next window
        if i < n - m:
            t_hash = (d * (t_hash - ord(text[i]) * h) + ord(text[i + m])) % q
            # We might get negative value of t_hash, converting it to positive
            if t_hash < 0:
                t_hash += q

# Example usage:
text = "ABCCBAABCCBA"
pattern = "ABCC"
rabin_karp_search(text, pattern)  # Output: Pattern found at index 0, Pattern found at index 8