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
-
s.length - 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 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
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 , and two windows are equal exactly when their numbers are. Sliding removes the oldest digit , worth , shifts the rest up a place and adds the new digit:
Slide a base-4 window one letter
Let's follow one slide with 4-letter windows, where the oldest digit is worth .
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 ; 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.
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 . For letter codes and a base , which plays the part 4 played above,
The window slides exactly as before, with every step taken modulo . Prefix hashes go further and need no sliding at all. We store the hash of every prefix once, , the hash of the first letters, together with the powers of . As in Python, s[l:r] stops just before position . The hash of s[0:r] is the hash of s[0:l] shifted up places plus the hash of s[l:r], so any substring hashes in a constant number of operations:
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]) % MFor 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 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 comparisons for substrings of length .
Deeper read: where the collision bound comes from
Take two different strings of length , with letter codes and . Their hashes are equal exactly when
The left side is a polynomial in of degree at most , and it is not zero: the strings differ somewhere, and every code is smaller than , so some is nonzero modulo . Such a polynomial has at most roots modulo a prime, so a base chosen at random after the input is fixed makes the two hashes equal with probability
That bound is per comparison, and over many comparisons the chances add up. A million substrings form about pairs. A modulus near fails here even if each pair collides with probability only : about pairs would share a hash. With , the bound above allows at most expected collisions, about for substrings of 100 letters.
Rolling-hash time and space
- Set of copied windows
- Each of about windows of letters is copied and hashed letter by letter.
- Rolling base-4 window
- Each slide takes out one digit and adds one.
- Prefix hashes
to build, per substring - One pass fills
preand the powers of . - Letter check after a hash match
per match - Comparing the two substrings rules out a collision.
Common mistakes
Multiplying by 4 before taking out the oldest digit.
- Where it breaks
- Text
CAAAAwith 4-letter windows:CAAAis 64, and the next windowAAAAcomes out as instead of 0, because after the multiply the C is worth 256. - The fix
- Subtract first, then multiply by 4 and add the new digit.
Trusting one hash mod with a fixed base across a million substrings.
- Where it breaks
- A million substrings form about pairs, far more than the hash values. If the substrings are all different, about 500 of those pairs are expected to share a hash, so the check almost certainly reports a repeat that is not there.
- The fix
- Use a random base modulo , or two independent hashes, or compare letters after a hash match.
Taking
(pre[r] - pre[l] * power[r - l]) % Mwith signed integers in C++.- Where it breaks
- C++'s
%keeps the sign of a negative difference, so two equal substrings can get values that differ by , one of them negative, and compare as different. Python's%always returns a value from 0 to . - The fix
- Add before the last
%, asgetdoes, and multiply throughunsigned __int128.
Recall Which tool answers which question?
The prefix function answers questions about borders or about matches ending at each position: KMP, periods, the longest happy prefix, the longest palindromic prefix. The Z-function answers how far each start matches the beginning of the string, as in the sum of scores. Both are exact and linear. A rolling hash compares many different substrings with each other, as in Repeated DNA Sequences. The base-4 numbers there are exact; a polynomial hash modulo a prime is very likely right, and certain only after we check the letters.