Basics 0/97

String matching: KMP, Z-function and rolling hashes · 2 of 2 Advanced

Rolling hashes

Turn substrings into numbers that update in constant time as a window slides, and compare any two substrings with prefix hashes.

1,126 words · 6 min read

Part 1 of 4 Rolling hashes

How can two substrings be compared in one step?

The prefix function and the Z-function both compare a string with its own beginning. Some problems instead compare many different substrings with each other. A hash turns a string into a number; equal strings get equal numbers, so comparing the numbers can replace comparing the letters. LeetCode's Repeated DNA Sequences compares every 10-letter substring with the others.

A DNA string uses the letters A, C, G and T. Return every 10-letter substring that occurs more than once, in any order.

Constraints

  • 1≤1 \le s.length ≤105\le 10^5
  • Each letter is A, C, G or T.

Sample 1 · Input

s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"

Output

["AAAAACCCCC","CCCCCAAAAA"]

Sample 2 · Input

s = "AAAAAAAAAAAAA"

Output

["AAAAAAAAAA"]

With windows of 10 letters, putting every substring into a set already works: about 105×10=10610^5 \times 10 = 10^6 letter operations. If the windows were 50,000 letters long, there would be about 50,000 of them, and copying and hashing each one letter by letter would cost

50,000×50,000=2.5×109 letter operations50{,}000 \times 50{,}000 = 2.5 \times 10^9 \text{ letter operations}

A rolling hash avoids that: when the window slides one letter, it updates the window's number in a few operations, however long the window is.

Give A, C, G and T the digits 0 to 3. A 10-letter window is then a 10-digit number in base 4, below 410=1,048,5764^{10} = 1{,}048{,}576, and two windows are equal exactly when their numbers are. Sliding removes the oldest digit coldc_{\text{old}}, worth cold×49c_{\text{old}} \times 4^9, shifts the rest up a place and adds the new digit:

hnext=(h−cold⋅49)⋅4+cnewh_{\text{next}} = \bigl(h - c_{\text{old}} \cdot 4^{9}\bigr) \cdot 4 + c_{\text{new}}

Slide a base-4 window one letter

Let's follow one slide with 4-letter windows, where the oldest digit is worth 43=644^3 = 64.

Subtract the leaving digit times 434^3, multiply by 4, add the entering digit. Check: 1⋅64+2⋅16+3⋅4+0=1081 \cdot 64 + 2 \cdot 16 + 3 \cdot 4 + 0 = 108.
def find_repeated_dna(s):
    code = {"A": 0, "C": 1, "G": 2, "T": 3}
    k = 10
    top = 4 ** (k - 1)
    seen, repeated = set(), set()
    h = 0
    for i, ch in enumerate(s):
        if i >= k:
            h -= code[s[i - k]] * top
        h = h * 4 + code[ch]
        if i >= k - 1:
            if h in seen:
                repeated.add(s[i - k + 1:i + 1])
            seen.add(h)
    return list(repeated)

On the first sample, returns AAAAACCCCC and CCCCCAAAAA in some order.

Slide the window one letter at a time

Each step brings in one letter. Until the window is full, a step computes h⋅4+cnewh \cdot 4 + c_{\text{new}}; after that it first takes out the oldest digit. A finished window whose number is already in the set is a repeat. Start with the figure's ACGTAC, then try both samples with 10-letter windows.

i012345 sACGTAC d012301

A, C, G and T are the digits 0 to 3, so each 4-letter window is a base-4 number. Its oldest digit is worth 4^3 = 64.

Repeated so far: none

On the all-A sample, every window is the number 0, so each window from index 1 on repeats the first one, and the answer lists AAAAAAAAAA once.

Hash any substring from prefix hashes

Ten base-4 digits fit in an integer, so that number is exact. A window of 50,000 letters is a 50,000-digit number, far too large to update in a few operations, so a polynomial hash keeps only its remainder after division by a large prime MM. For letter codes c0,…,ck−1c_0, \dots, c_{k-1} and a base BB, which plays the part 4 played above,

h(c0c1…ck−1)=(c0Bk−1+c1Bk−2+⋯+ck−1) mod Mh(c_0 c_1 \dots c_{k-1}) = \bigl(c_0 B^{k-1} + c_1 B^{k-2} + \dots + c_{k-1}\bigr) \bmod M

The window slides exactly as before, with every step taken modulo MM. Prefix hashes go further and need no sliding at all. We store the hash of every prefix once, pre[i]=h(s[0:i])\text{pre}[i] = h(s[0:i]), the hash of the first ii letters, together with the powers of BB. As in Python, s[l:r] stops just before position rr. The hash of s[0:r] is the hash of s[0:l] shifted up r−lr - l places plus the hash of s[l:r], so any substring hashes in a constant number of operations:

h(s[l:r])=(pre[r]−pre[l]⋅B r−l) mod Mh(s[l:r]) = \bigl(\text{pre}[r] - \text{pre}[l] \cdot B^{\,r-l}\bigr) \bmod M
M = (1 << 61) - 1
B = random.randrange(256, M - 1)

def prefix_hashes(s):
    pre, power = [0], [1]
    for ch in s:
        pre.append((pre[-1] * B + ord(ch)) % M)
        power.append(power[-1] * B % M)
    return pre, power

def substring_hash(pre, power, l, r):  # hash of s[l:r]
    return (pre[r] - pre[l] * power[r - l]) % M

For s = "abcxabc", the hashes of s[0:3] and s[4:7] are equal.

Different strings can share a hash, which is called a collision. With M=261−1M = 2^{61} - 1 and a base chosen at random when the program runs, two different strings of 100,000 letters collide with probability below about 1 in 23 trillion. A fixed, well-known base gives no such guarantee, because a test can be built against it. Comparing the letters of two substrings whose hashes match makes the answer certain, at a cost of up to LL comparisons for substrings of length LL.

Deeper read: where the collision bound comes from

Take two different strings of length LL, with letter codes c0,…,cL−1c_0, \dots, c_{L-1} and d0,…,dL−1d_0, \dots, d_{L-1}. Their hashes are equal exactly when

∑i=0L−1(ci−di) BL−1−i≡0(modM)\sum_{i=0}^{L-1} (c_i - d_i)\, B^{L-1-i} \equiv 0 \pmod M

The left side is a polynomial in BB of degree at most L−1L - 1, and it is not zero: the strings differ somewhere, and every code is smaller than MM, so some ci−dic_i - d_i is nonzero modulo MM. Such a polynomial has at most L−1L - 1 roots modulo a prime, so a base chosen at random after the input is fixed makes the two hashes equal with probability

Pr⁡[collision]≤L−1M<105261−1≈123×1012\Pr[\text{collision}] \le \frac{L - 1}{M} < \frac{10^5}{2^{61} - 1} \approx \frac{1}{23 \times 10^{12}}

That bound is per comparison, and over many comparisons the chances add up. A million substrings form about 1012/2=5×101110^{12} / 2 = 5 \times 10^{11} pairs. A modulus near 10910^9 fails here even if each pair collides with probability only 1/M1 / M: about 5×1011/109=5005 \times 10^{11} / 10^9 = 500 pairs would share a hash. With M=261−1≈2.3×1018M = 2^{61} - 1 \approx 2.3 \times 10^{18}, the bound above allows at most 5×1011×(L−1)/M5 \times 10^{11} \times (L - 1) / M expected collisions, about 2×10−52 \times 10^{-5} for substrings of 100 letters.