String HashingString hashing

01Why it exists

Reach for it when you see:Checking a great many pairs of substrings for equality, putting substrings into a set or hash table, binary searching a length to find the longest repeat, longest common prefixes, lexicographic comparison — and a vanishingly small chance of being wrong is acceptable.

02The core idea

Comparing two strings of length L means comparing them character by character, O(L). Hashing turns a string into a single number instead: read the string as a number written in base B, one digit per character, hash(s) = s[0]·B^(L−1) + s[1]·B^(L−2) + … + s[L−1], all taken mod a large prime M. That is a polynomial hash. It accumulates from left to right — h[i+1] = h[i]·B + s[i] — so one pass gives you every prefix hash, and you store pw[i] = B^i along the way. No character may have the value 0: if a = 0 then "a" and "aa" both hash to 0, the same way 007 and 7 are indistinguishable, so start counting at a = 1 or just use the character codes.

With the prefix hashes in hand, the hash of any substring s[l, r) comes out in O(1). h[r] is the number formed by the first r characters, inside which the first l characters have been scaled by an extra B^(r−l), so hash(l, r) = h[r] − h[l]·pw[r−l]. It is the same move as stripping the leading 12 off 12345 in decimal: 12345 − 12 × 1000 = 345. Building the tables costs O(n) time and O(n) space, and every equality check afterwards is O(1). The rule for reading the result only runs one way: different hashes mean the strings definitely differ; equal hashes mean they almost certainly match.

How likely is a collision? For two distinct strings of length at most n, the difference of their hashes is a polynomial of degree below n, which has at most n−1 roots mod the prime M. So with a randomly chosen base B the collision probability is at most (n−1)/M, and in practice close to 1/M. The real danger is comparing many things at once: drop q hashes into a set and the expected number of colliding pairs is about q²/(2M). At q = 10⁵ and M ≈ 10⁹ that expectation is already 5 pairs, which is why real code uses M = 2⁶¹−1, or two primes near 10⁹ computed separately (double hashing), pushing the expectation below 10⁻⁸. The base must be random: a fixed base lets someone construct collisions in advance, and "Aa" against "BB" is one such pair for Java's string hash.

The usual traps: in C++ h[r] − h[l]·pw can go negative, so add M before taking the modulus; multiplying two numbers around 10⁹ needs 64-bit integers, and with the modulus 2⁶¹−1 even 64 bits are not enough, so you need 128-bit multiplication or split the operands. Taking the shortcut of letting an unsigned long long overflow naturally (which is mod 2⁶⁴) is worse: 2⁶⁴ is not prime, and the Thue–Morse string of length 1024 collides with its a/b-swapped twin for every odd base you could pick. When the answer has to be exactly right, confirm character by character after the hashes match. How this sits next to the neighbouring lessons: Rabin-Karp, coming up next, slides a fixed-length window along the string and updates the hash in O(1) per step, while KMP and the Z-Algorithm are fully deterministic with no collision risk at all — they just answer a narrower set of questions than hashing does.

03The algorithm

1. 1Pick a large prime M (2⁶¹−1 is common, or use 10⁹+7 and 998244353 together) and draw the base B at random from [256, M) when the program starts.
2. 2Build the tables left to right: h[0] = 0, pw[0] = 1, h[i+1] = (h[i]·B + s[i]) mod M, pw[i+1] = pw[i]·B mod M.
3. 3Take the hash of a substring s[l, r) as (h[r] − h[l]·pw[r−l]) mod M, adding M if the result came out negative.
4. 4Compare two ranges: different lengths or different hashes mean they definitely differ; equal hashes count as equal, and when the answer has to be exact, confirm character by character.
5. 5For the longest repeat or the longest common prefix, binary search the length using the fact that if L works so does L−1, and make every check an O(1) substring hash.

04Interactive demo

s = abcabca, with base B = 31 and modulus M = 101 so the arithmetic stays doable by hand, and character values a = 1, b = 2, c = 3. The first half builds the tables one character at a time: blue marks the character just read and the h and pw values just computed, and the box spells out the arithmetic for that step. Once the tables are built, three comparisons follow: yellow marks the first range together with the h and pw cells the formula uses, and the second range turns green when its hash matches and blue when it does not. s[0, 3) and s[3, 6) are both abc and both hash to 16; s[1, 4) and s[4, 7) are both bca and both hash to 97; abc against bca is 16 against 97, which must differ, so no character-by-character check is needed. M = 101 only has 101 possible values, so collisions appear as soon as there are many substrings — in real use, switch to one of the large moduli above.

05Code

Python uses the single modulus 2⁶¹−1 (Python integers never overflow), demonstrates substring comparison and the binary search for the longest repeated block, and finally reproduces the Java string-hash collision. C++ uses the two moduli 10⁹+7 and 998244353, keeps every multiplication inside 64 bits, and sorts suffixes by binary searching their longest common prefix with hashes. Both languages randomise the base at startup, so the hash values differ on every run while the printed answers stay the same.

import random


class PrefixHash:
    """Polynomial prefix hashing: O(n) to build, then O(1) for any substring s[l:r]"""
    M = (1 << 61) - 1                   # Mersenne prime; Python ints never overflow, so use it directly
    B = random.randrange(256, M)        # random base: nobody can construct collisions ahead of time

    def __init__(self, s):
        n = len(s)
        self.h = [0] * (n + 1)          # h[i] = hash of s[:i]
        self.pw = [1] * (n + 1)         # pw[i] = B^i mod M
        for i, ch in enumerate(s):
            self.h[i + 1] = (self.h[i] * self.B + ord(ch)) % self.M   # code points are never 0
            self.pw[i + 1] = self.pw[i] * self.B % self.M

    def get(self, l, r):
        """Hash of s[l:r]: inside h[r] the first l characters were scaled by B^(r-l), so subtract that"""
        return (self.h[r] - self.h[l] * self.pw[r - l]) % self.M   # Python's % is never negative


def longest_duplicate(s):
    """Longest substring occurring at least twice (overlaps allowed). If length L repeats, so does L-1, so binary search the length"""
    ph = PrefixHash(s)

    def find(L):                        # a start index of some length-L substring seen twice, or -1
        seen = set()
        for i in range(len(s) - L + 1):
            x = ph.get(i, i + L)
            if x in seen:
                return i
            seen.add(x)
        return -1

    lo, hi, best = 1, len(s) - 1, ""
    while lo <= hi:                     # O(n) per guess, O(n log n) in total
        mid = (lo + hi) // 2
        i = find(mid)
        if i == -1:
            hi = mid - 1
        else:
            best, lo = s[i:i + mid], mid + 1
    return best


def java_hash(s):
    """Java's String.hashCode: fixed base 31, natural overflow (mod 2³²)"""
    x = 0
    for ch in s:
        x = (x * 31 + ord(ch)) & 0xFFFFFFFF
    return x


if __name__ == "__main__":
    ph = PrefixHash("abcabca")
    print(ph.get(0, 3) == ph.get(3, 6), ph.get(0, 3) == ph.get(1, 4))   # True False
    print(longest_duplicate("banana"), longest_duplicate("to be or not to be"))   # ana to be
    print(repr(longest_duplicate("abcd")))                              # ''
    print(java_hash("Aa"), java_hash("BB"), java_hash("AaBB"), java_hash("BBAa"))   # 2112 2112 2031744 2031744

06Practice

• LeetCode 187Repeated DNA Sequences (fixed length 10, hashes into a set)Medium
• LeetCode 718Maximum Length of Repeated Subarray (arrays hash too; binary search the length)Medium
• LeetCode 1044Longest Duplicate Substring (binary search plus a hash set; mind the collisions)Hard
• LeetCode 1147Longest Chunked Palindrome Decomposition (greedy from both ends, hashing to compare the two chunks)Hard
• LeetCode 1316Distinct Echo Substrings (substring hashes to test the two halves, then deduplicate)Hard
• LeetCode 2223Sum of Scores of Built Strings (common prefix of each suffix with the whole string, by binary search; the Z-Algorithm lesson revisits it)Hard