String Hashing Techniques for Pattern Matching

String hashing converts a string into a number. If two strings have different hashes, they are definitely different. If they have the same hash, they are probably the same (but you must verify). This “probably” is what makes hashing tricky — and powerful. Done right, it gives you O(1) string comparisons and O(n) pattern matching. Done wrong, it gives you collisions and wrong answers.

Polynomial hashing

The most common string hash function treats the string as a polynomial in some base b, evaluated modulo a large prime p:

hash("abc") = (a * b^2 + b * b^1 + c * b^0) mod p

Where each character is converted to a number (e.g., ord(ch) - ord('a') + 1).

def polynomial_hash(s: str, base: int = 31, mod: int = 10**9 + 7) -> int:
    h = 0
    power = 1
    for ch in s:
        h = (h + (ord(ch) - ord('a') + 1) * power) % mod
        power = (power * base) % mod
    return h

Why base 31 and mod 10^9 + 7?

• Base 31: Larger than the alphabet size (26), and prime. This minimizes collisions between different strings.
• Mod 10^9 + 7: A large prime that fits in a 64-bit integer. Keeps hash values manageable while making collisions rare.

Alternative: hash from the left

Some implementations evaluate from left to right using Horner’s method:

def polynomial_hash_left(s: str, base: int = 31, mod: int = 10**9 + 7) -> int:
    h = 0
    for ch in s:
        h = (h * base + (ord(ch) - ord('a') + 1)) % mod
    return h

Both approaches work. The left-to-right version is slightly easier to extend to rolling hashes.

Rolling hash

The key insight that powers Rabin-Karp: when you slide a window of length L one position to the right, you can update the hash in O(1) instead of recomputing it from scratch in O(L).

If the hash of s[i..i+L-1] is known, the hash of s[i+1..i+L] is:

new_hash = (old_hash - s[i] * b^0) / b + s[i+L] * b^(L-1)

Using the left-to-right convention (Horner’s method):

new_hash = (old_hash - s[i] * b^(L-1)) * b + s[i+L]

All operations are mod p.

def rolling_hash_demo(s: str, window_len: int):
    base = 31
    mod = 10**9 + 7
    n = len(s)

    if n {'<'} window_len:
        return

    # Precompute base^(window_len - 1) mod p
    power = pow(base, window_len - 1, mod)

    # Compute hash of first window
    h = 0
    for i in range(window_len):
        h = (h * base + (ord(s[i]) - ord('a') + 1)) % mod

    print(f"Window '{s[0:window_len]}' -> hash {h}")

    # Slide the window
    for i in range(1, n - window_len + 1):
        # Remove leftmost character, add new rightmost character
        old_char = ord(s[i - 1]) - ord('a') + 1
        new_char = ord(s[i + window_len - 1]) - ord('a') + 1
        h = (h - old_char * power % mod + mod) % mod
        h = (h * base + new_char) % mod

        print(f"Window '{s[i:i+window_len]}' -> hash {h}")

Key detail: When subtracting, add mod before taking % mod to avoid negative values.

Rabin-Karp algorithm

Rabin-Karp uses rolling hash for pattern matching. Instead of comparing the pattern against every position (O(n * m) brute force), it compares hashes (O(1) each) and only does a full comparison on hash matches.

def rabin_karp(text: str, pattern: str) -> list:
    base = 31
    mod = 10**9 + 7
    n, m = len(text), len(pattern)

    if m > n:
        return []

    # Compute hash of pattern
    pattern_hash = 0
    for ch in pattern:
        pattern_hash = (pattern_hash * base + (ord(ch) - ord('a') + 1)) % mod

    # Compute hash of first window in text
    text_hash = 0
    for i in range(m):
        text_hash = (text_hash * base + (ord(text[i]) - ord('a') + 1)) % mod

    # Precompute base^(m-1) mod p
    power = pow(base, m - 1, mod)

    result = []

    for i in range(n - m + 1):
        # Compare hashes
        if text_hash == pattern_hash:
            # Verify to avoid false positives
            if text[i:i + m] == pattern:
                result.append(i)

        # Roll the hash (if not at the last position)
        if i {'<'} n - m:
            old_char = ord(text[i]) - ord('a') + 1
            new_char = ord(text[i + m]) - ord('a') + 1
            text_hash = (text_hash - old_char * power % mod + mod) % mod
            text_hash = (text_hash * base + new_char) % mod

    return result

Example

text = "aabaabaabaab"
pattern = "aab"
print(rabin_karp(text, pattern))  # [0, 3, 6]

Complexity analysis

• Best/average case: O(n + m) — hash comparisons are O(1) and collisions are rare.
• Worst case: O(n * m) — if every position has a hash match (many collisions). This happens with pathological inputs and a bad hash function.
• Space: O(1) extra (not counting the output list).

Multi-pattern Rabin-Karp

To search for multiple patterns simultaneously, compute the hash of each pattern and store them in a set. Slide the window once, checking the hash against all patterns:

def rabin_karp_multi(text: str, patterns: list) -> dict:
    base = 31
    mod = 10**9 + 7

    # Group patterns by length
    by_length = {}
    for pat in patterns:
        by_length.setdefault(len(pat), []).append(pat)

    result = {pat: [] for pat in patterns}

    for m, pats in by_length.items():
        if m > len(text):
            continue

        # Hash all patterns of this length
        pat_hashes = {}
        for pat in pats:
            h = 0
            for ch in pat:
                h = (h * base + (ord(ch) - ord('a') + 1)) % mod
            pat_hashes.setdefault(h, []).append(pat)

        # Hash first window
        text_hash = 0
        for i in range(m):
            text_hash = (text_hash * base + (ord(text[i]) - ord('a') + 1)) % mod
        power = pow(base, m - 1, mod)

        for i in range(len(text) - m + 1):
            if text_hash in pat_hashes:
                window = text[i:i + m]
                for pat in pat_hashes[text_hash]:
                    if window == pat:
                        result[pat].append(i)

            if i {'<'} len(text) - m:
                old_char = ord(text[i]) - ord('a') + 1
                new_char = ord(text[i + m]) - ord('a') + 1
                text_hash = (text_hash - old_char * power % mod + mod) % mod
                text_hash = (text_hash * base + new_char) % mod

    return result

Time: O(n * k) where k is the number of distinct pattern lengths, plus O(sum of pattern lengths) for hashing.

Double hashing

A single hash has a collision probability of about 1/p for each comparison. Over n comparisons, the probability of at least one collision is roughly n/p. For n = 10^6 and p = 10^9 + 7, this is about 0.1% — often acceptable, but not always.

Double hashing uses two independent hash functions. A false positive requires both hashes to collide simultaneously, reducing the probability to (n/p1) * (n/p2).

def double_hash(s: str) -> tuple:
    mod1 = 10**9 + 7
    mod2 = 10**9 + 9
    base1 = 31
    base2 = 37

    h1, h2 = 0, 0
    for ch in s:
        val = ord(ch) - ord('a') + 1
        h1 = (h1 * base1 + val) % mod1
        h2 = (h2 * base2 + val) % mod2

    return (h1, h2)

Rolling double hash

class RollingDoubleHash:
    def __init__(self, s: str, window_len: int):
        self.s = s
        self.m = window_len
        self.mod1 = 10**9 + 7
        self.mod2 = 10**9 + 9
        self.base1 = 31
        self.base2 = 37

        self.power1 = pow(self.base1, window_len - 1, self.mod1)
        self.power2 = pow(self.base2, window_len - 1, self.mod2)

        # Compute initial hash
        self.h1 = 0
        self.h2 = 0
        for i in range(window_len):
            val = ord(s[i]) - ord('a') + 1
            self.h1 = (self.h1 * self.base1 + val) % self.mod1
            self.h2 = (self.h2 * self.base2 + val) % self.mod2

    def get(self) -> tuple:
        return (self.h1, self.h2)

    def roll(self, old_char: str, new_char: str) -> tuple:
        old_val = ord(old_char) - ord('a') + 1
        new_val = ord(new_char) - ord('a') + 1

        self.h1 = (self.h1 - old_val * self.power1 % self.mod1 + self.mod1) % self.mod1
        self.h1 = (self.h1 * self.base1 + new_val) % self.mod1

        self.h2 = (self.h2 - old_val * self.power2 % self.mod2 + self.mod2) % self.mod2
        self.h2 = (self.h2 * self.base2 + new_val) % self.mod2

        return (self.h1, self.h2)

Problem 1: Repeated DNA Sequences

LeetCode 187. Find all 10-letter-long sequences that occur more than once in a DNA string.

Approach

Use rolling hash with a window of size 10. Track seen hashes and collect duplicates.

def find_repeated_dna(s: str) -> list:
    if len(s) {'<'}= 10:
        return []

    base = 4  # DNA has 4 characters
    mod = 10**9 + 7
    window = 10

    # Map DNA characters to numbers
    char_to_num = {'A': 0, 'C': 1, 'G': 2, 'T': 3}

    # Compute hash of first window
    h = 0
    power = pow(base, window - 1, mod)
    for i in range(window):
        h = (h * base + char_to_num[s[i]]) % mod

    seen = {h}
    duplicates = set()
    result = []

    for i in range(1, len(s) - window + 1):
        # Roll hash
        old_val = char_to_num[s[i - 1]]
        new_val = char_to_num[s[i + window - 1]]
        h = (h - old_val * power % mod + mod) % mod
        h = (h * base + new_val) % mod

        if h in seen:
            # Verify (or use double hash to skip verification)
            substr = s[i:i + window]
            if substr not in duplicates:
                duplicates.add(substr)
                result.append(substr)
        else:
            seen.add(h)

    return result

Simpler approach with Python’s built-in hashing

For interview purposes, Python’s built-in hashing is often acceptable:

def find_repeated_dna_simple(s: str) -> list:
    seen = set()
    result = set()

    for i in range(len(s) - 9):
        substr = s[i:i + 10]
        if substr in seen:
            result.add(substr)
        else:
            seen.add(substr)

    return list(result)

Time: O(n * 10) for substring creation = O(n). Rolling hash version is O(n) with O(1) per step. Space: O(n) for the sets.

Bit manipulation alternative

Since DNA has only 4 characters (2 bits each), a 10-character sequence fits in 20 bits:

def find_repeated_dna_bits(s: str) -> list:
    char_to_bits = {'A': 0, 'C': 1, 'G': 2, 'T': 3}
    mask = (1 {'<'}{'<'} 20) - 1  # 20-bit mask

    if len(s) {'<'}= 10:
        return []

    h = 0
    for i in range(10):
        h = (h {'<'}{'<'} 2) | char_to_bits[s[i]]

    seen = {h}
    result = set()

    for i in range(1, len(s) - 9):
        h = ((h {'<'}{'<'} 2) | char_to_bits[s[i + 9]]) & mask
        if h in seen:
            result.add(s[i:i + 10])
        else:
            seen.add(h)

    return list(result)

Time: O(n). Space: O(n). No collisions possible since the hash is perfect for 10-character DNA strings.

Problem 2: Longest Duplicate Substring

LeetCode 1044. Given a string s, return the longest substring that appears at least twice. If no such substring exists, return "".

Approach: Binary search + rolling hash

The key insight: if a duplicate substring of length k exists, then a duplicate of length k-1 also exists (just take any k-length duplicate and drop the last character). This monotonicity lets us binary search on the answer length.

For each candidate length, use rolling hash to check if any substring of that length appears twice.

def longest_dup_substring(s: str) -> str:
    n = len(s)
    base1 = 31
    mod1 = 10**18 + 9
    base2 = 37
    mod2 = 10**18 + 7

    def check(length: int) -> str:
        """Check if any substring of given length appears twice.
        Returns the duplicate substring or empty string."""
        if length == 0:
            return ""

        # Compute initial hash
        h1, h2 = 0, 0
        power1 = pow(base1, length - 1, mod1)
        power2 = pow(base2, length - 1, mod2)

        for i in range(length):
            val = ord(s[i]) - ord('a') + 1
            h1 = (h1 * base1 + val) % mod1
            h2 = (h2 * base2 + val) % mod2

        seen = {(h1, h2): 0}

        for i in range(1, n - length + 1):
            old_val = ord(s[i - 1]) - ord('a') + 1
            new_val = ord(s[i + length - 1]) - ord('a') + 1

            h1 = (h1 - old_val * power1 % mod1 + mod1) % mod1
            h1 = (h1 * base1 + new_val) % mod1

            h2 = (h2 - old_val * power2 % mod2 + mod2) % mod2
            h2 = (h2 * base2 + new_val) % mod2

            key = (h1, h2)
            if key in seen:
                return s[i:i + length]
            seen[key] = i

        return ""

    # Binary search on length
    lo, hi = 0, n - 1
    result = ""

    while lo {'<'}= hi:
        mid = (lo + hi) // 2
        dup = check(mid)
        if dup:
            result = dup
            lo = mid + 1
        else:
            hi = mid - 1

    return result

Walkthrough

For s = "banana":

• Binary search tries length 3: check substrings ban, ana, nan, ana — ana appears twice. Found.
• Try length 4: bana, anan, nana — all unique. Not found.
• Try length 3 again (already confirmed). Answer: "ana".

Time complexity: O(n log n) — binary search is O(log n) and each check is O(n). Space complexity: O(n) for the hash set.

Why double hashing matters here

With n up to 3 * 10^4 in the LeetCode version (or larger in follow-ups), single hashing with mod 10^9 + 7 gives collision probability around n^2 / mod ~ 10^8 / 10^9 = 10%, which is too high. Double hashing reduces this to effectively zero.

Choosing hash parameters

Parameter	Recommendation	Why
Base	31 or 37	Prime, larger than alphabet
Modulus	10^9 + 7 or 10^9 + 9	Large prime, fits in 64-bit int
Double hash	Use for competitive/critical code	Reduces collision probability to ~0

Collision probability analysis

For a single hash with modulus p and n comparisons:

• Probability of any collision: approximately n^2 / (2 * p) (birthday paradox).
• With p = 10^9 + 7 and n = 10^5: probability ~ 10^10 / (2 * 10^9) = 5. This means collisions are almost certain.
• With double hash: probability ~ n^2 / (2 * p1) * n^2 / (2 * p2) ~ 10^{-8}. Safe.

Rule of thumb: Always use double hashing when the number of hash comparisons exceeds sqrt(mod).

Rabin-Karp vs KMP vs Z-algorithm

Algorithm	Time	Space	Best For
Rabin-Karp	O(n+m) avg, O(nm) worst	O(1)	Multi-pattern, simple to code
KMP	O(n+m) guaranteed	O(m)	Single pattern, guaranteed linear
Z-algorithm	O(n+m) guaranteed	O(n)	Single pattern, prefix queries
Aho-Corasick	O(n + m + z)	O(m * alphabet)	Many patterns simultaneously

Rabin-Karp is the easiest to implement and the only one that naturally extends to 2D pattern matching (matching a small matrix inside a large one). Its weakness is the probabilistic nature — worst case is quadratic with bad hash functions.

Common mistakes

1. Forgetting + mod before % mod when subtracting. Without this, you get negative values and wrong hashes.
2. Using too small a modulus. Mod 10^6 + 3 gives frequent collisions. Use at least 10^9 + 7.
3. Not verifying on hash match. Always compare the actual strings when hashes match, unless you are using double hashing and are confident.
4. Using base = 26 for lowercase letters. If a maps to 0, then "a" and "aa" and "aaa" all hash to 0. Use ord(ch) - ord('a') + 1 (1-indexed) or a base larger than 26.
5. Integer overflow in languages like C++ and Java. Python handles big integers natively, but in other languages you need to take mod at every step.

Practice problems

1. LeetCode 28 — Find the Index of the First Occurrence in a String
2. LeetCode 187 — Repeated DNA Sequences
3. LeetCode 1044 — Longest Duplicate Substring
4. LeetCode 686 — Repeated String Match
5. LeetCode 1062 — Longest Repeating Substring
6. LeetCode 718 — Maximum Length of Repeated Subarray
7. LeetCode 214 — Shortest Palindrome (rolling hash approach)
8. LeetCode 1147 — Longest Chunked Palindrome Decomposition
9. LeetCode 1316 — Distinct Echo Substrings
10. LeetCode 572 — Subtree of Another Tree (tree hashing variant)

Final thoughts

String hashing is a probabilistic tool. It trades certainty for speed — O(1) comparisons instead of O(L). The rolling hash is what makes it practical: updating the hash as a window slides is the key to Rabin-Karp and all the problems built on top of it.

The two things to internalize are the rolling hash update formula and the importance of double hashing for correctness. Get these right and string hashing becomes a reliable weapon in your interview arsenal. Get them wrong and you will debug phantom collisions for hours.