String Hashing in Depth
Why this exists
Comparing two strings letter by letter costs time proportional to their length. That is fine once. It is not fine when an algorithm compares substrings millions of times: "is this window equal to the pattern?", "does any substring of length 40 appear twice?", "is the first half of this piece equal to the second half?". Each question costs , and the questions pile up into or work.
String hashing turns every substring into a single number, its fingerprint, so that comparing two substrings becomes comparing two numbers: . After an preparation pass over the string, you can get the fingerprint of any substring in . Equal strings always get equal fingerprints. Unequal strings get different fingerprints with very high probability, and this lesson makes that "very high" precise and shows how to keep it high even when someone is actively trying to break your code.
An everyday analogy: a library does not compare two books page by page to decide whether they are the same edition. It compares the ISBN. Two copies of the same edition always share an ISBN; two different books almost never do. A string hash is an ISBN that you can compute for any excerpt of a book, instantly, after one pass through it.
The idea goes back to Richard Karp and Michael Rabin ("Efficient randomized pattern-matching algorithms", IBM Journal of Research and Development, 1987), who used it to search for a pattern in a text. That algorithm, Rabin–Karp, is in this lesson, but the real payoff of hashing is broader: it is the most flexible tool in the string toolbox. KMP, the Z-algorithm and Aho–Corasick each solve one family of problems perfectly. Hashing solves a little of almost everything, in a few lines, as long as you respect its one weakness: collisions.
This is lesson 2 of Module 7. You need Hash Tables for the general idea of hashing, Prefix Sums (prefix hashes are prefix sums in disguise), Sliding Window for Rabin–Karp, and Binary Search for the applications.
Pattern triggers
| If the problem says or has… | Think of… |
|---|---|
| "compare many substrings for equality", "are these two pieces equal" | Prefix hashes: substring equality |
| "find a pattern in a text" and you want ten lines of code | Rabin–Karp (or KMP / Z for a deterministic guarantee) |
| "longest substring that appears twice / in both strings / in all strings" | Binary search on the length + a set of hashes |
| "count distinct substrings" (small ) | Hash every substring into a per-length set |
| "longest prefix that is also a suffix", "is a rotation of " | Compare prefix and suffix hashes |
| "is a palindrome?" asked many times | Forward hash vs reverse hash |
| "many patterns, all the same length" | Put the pattern hashes in a set, roll one window |
| "lexicographically compare two substrings" | Binary search the first difference with hashes (LCP by hashing) |
| "deduplicate files / chunks / documents" | Rolling hash fingerprints, content-defined chunking |
| "strings are updated (point changes) between queries" | Hashes in a Fenwick or segment tree |
The meta-trigger: you need to compare substrings, and you need it fast and often. If a wrong answer with probability is acceptable (it nearly always is, given the right parameters), hashing is usually the shortest correct solution.
Intuition & first principles
Step 1: turn a word into a number
Give each letter a value: a = 1, b = 2, c = 3, and so on up to z = 26. Now read a word as the digits of a number. In base 10, "cab" is the digits 3, 1, 2, so
This is how you already read numbers: the leftmost digit is worth the most. Two different words with letters a to i always give two different numbers, because two different digit strings of the same length are two different numbers.
But letters go up to 26 and digits only go up to 9. In base 10, the word "ak" is and the word "ba" is . Same number, different words. The fix is the same as in any number system: the base must be larger than every digit. With base 27 or more, every letter is a single "digit", and different words of the same length give different numbers again. We will usually use in hand examples:
Why not give a = 0? Because then "a", "aa" and "aaa" would all be 0, just as 0, 00 and 000 are the same number. Leading zeros vanish. Start the letter values at 1 (or use the character code, which is never 0 for printable text).
You do not compute powers to evaluate this. You use Horner's rule: start at 0, and for each letter, multiply by the base and add the letter.
One multiplication and one addition per letter. Reading a string left to right builds its number.
Step 2: keep the number small
The number for a 20-letter word is around , far too big for a machine word. So we keep only the remainder modulo a large prime , for example . That gives the polynomial hash:
where is the value of the -th character and is the length. Horner's rule still works: take the remainder after every step, , and the numbers never exceed about .
The price of taking remainders is collisions: two different strings can now land on the same remainder, because there are infinitely many strings and only remainders. Most of this lesson is about making collisions so unlikely that you can ignore them, and about what to do when you cannot.
Step 3: the rolling trick
Say you know the hash of the window "abr" and want the hash of the next window "bra". In decimal terms: you know 123 and want 234. Remove the leading digit's contribution (), shift left (), add the new digit (). Three cheap operations, no matter how long the window is. With hashes:
That is a rolling hash: a fixed-length window slides along the text and its hash is updated in per step. It is the engine of Rabin–Karp.
Step 4: any substring, not just windows
Sliding works for one fixed window length. To get the hash of any substring in , store the hash of every prefix. In decimal: the prefixes of "314159" are 3, 31, 314, 3141, 31415, 314159. To get the digits at positions 2 to 4 ("415"), take the prefix that ends at position 4 (31415) and subtract the shorter prefix (31) shifted left by three places (31000):
The same subtraction works for hashes. That is the whole idea of prefix hashes, and it is the same idea as prefix sums, with "shift then subtract" instead of plain "subtract".
flowchart LR
S["string s"] --> V["letters to values<br/>a=1 ... z=26"]
V --> H["Horner: h = h*B + v"]
H --> MOD["keep h mod M"]
MOD --> P["prefix hashes<br/>h of every prefix"]
P --> Q["hash of any substring<br/>in O(1)"]
Q --> C["compare numbers<br/>instead of letters"]
Mechanics
Prefix hashes
Let h[0] = 0 and h[i+1] = (h[i] * B + v(s[i])) mod M, so h[i] is the hash of the first characters. Also precompute the powers p[k] = B^k mod M. Then the hash of the half-open slice (characters to , length ) is
Why it works: unrolling Horner, is the hash of shifted left by places, plus the hash of :
Rearrange and you have the formula. It is the decimal subtraction above, done modulo .
Half-open intervals
Use : start included, end excluded. The length is simply , the empty substring is , and h has entries. Closed intervals work too but cause most off-by-one bugs in hashing code.
Dry run: prefix hashes of "banana"
, , a = 1, b = 2, n = 14. The numbers stay below here, so you can check every value with a calculator; on longer strings the remainder kicks in.
h[i] (before) | h[i+1] = h[i]·31 + v | p[i+1] = 31^(i+1) | |||
|---|---|---|---|---|---|
| — | — | — | — | h[0] = 0 | p[0] = 1 |
| 0 | b | 2 | 0 | 0·31 + 2 = 2 | 31 |
| 1 | a | 1 | 2 | 2·31 + 1 = 63 | 961 |
| 2 | n | 14 | 63 | 63·31 + 14 = 1967 | 29791 |
| 3 | a | 1 | 1967 | 1967·31 + 1 = 60978 | 923521 |
| 4 | n | 14 | 60978 | 60978·31 + 14 = 1890332 | 28629151 |
| 5 | a | 1 | 1890332 | 1890332·31 + 1 = 58600293 | 887503681 |
Now compare the two copies of "ana", at and :
| Query | Formula | Value |
|---|---|---|
| hash(1, 4) = "ana" | h[4] - h[1]·p[3] = 60978 − 2·29791 | 1396 |
| hash(3, 6) = "ana" | h[6] - h[3]·p[3] = 58600293 − 1967·29791 | 1396 |
| hash(0, 2) = "ba" | h[2] - h[0]·p[2] = 63 − 0 | 63 |
| hash(2, 4) = "na" | h[4] - h[2]·p[2] = 60978 − 63·961 | 435 |
| hash(4, 6) = "na" | h[6] - h[4]·p[2] = 58600293 − 60978·961 | 435 |
And directly: "ana" . Equal substrings, equal numbers, each found with one multiplication and one subtraction. (All values were checked by running the code in the Implementation section.)
Rabin–Karp: rolling a window over the text
To find pattern (length ) in text (length ):
- Hash the pattern: .
- Hash the first window : .
- For each window start : if , compare the letters to confirm; then roll one step right.
RabinKarp(T, P):
top = B^(m-1) mod M # weight of the window's first letter
hp = hash(P); hw = hash(T[0:m])
for i = 0 .. n-m:
if hw == hp and T[i:i+m] == P: # equal hashes are only a hint
report i
if i + m < n:
hw = ((hw - v(T[i]) * top) * B + v(T[i+m])) mod M
The letter check in step 3 is what makes the algorithm always correct. A hash match is a candidate; the comparison confirms it. A wrong candidate is called a spurious hit. Without the check, Rabin–Karp is a fast algorithm that is occasionally wrong (a "Monte Carlo" algorithm). With it, it is always right and only occasionally slow (a "Las Vegas" algorithm).
Dry run: Rabin–Karp with a deliberately tiny modulus
To make a spurious hit happen on a small example, use a silly modulus: , so every hash is one of 0..10. Text "abracadabra", pattern "abra", , a = 1, b = 2, c = 3, d = 4, r = 18. Then , and .
| Window | Window | Equal to 9? | Letter check | Roll to next window: | |
|---|---|---|---|---|---|
| 0 | abra | 9 | yes | match at 0 | ((9 − 1·3)·31 + 3) mod 11 = 2 |
| 1 | brac | 2 | no | — | ((2 − 2·3)·31 + 1) mod 11 = 9 |
| 2 | raca | 9 | yes | "raca" ≠ "abra": spurious | ((9 − 18·3)·31 + 4) mod 11 = 6 |
| 3 | acad | 6 | no | — | ((6 − 1·3)·31 + 1) mod 11 = 6 |
| 4 | cada | 6 | no | — | ((6 − 3·3)·31 + 2) mod 11 = 8 |
| 5 | adab | 8 | no | — | ((8 − 1·3)·31 + 18) mod 11 = 8 |
| 6 | dabr | 8 | no | — | ((8 − 4·3)·31 + 1) mod 11 = 9 |
| 7 | abra | 9 | yes | match at 7 | (last window) |
Matches: [0, 7]. Six of the eight windows were rejected after one number comparison, without reading their letters. One window fooled the hash and was caught by the letter check. With instead of 11, a spurious hit on this input is essentially impossible; we will compute exactly how impossible below.
Step through it: the shaded cells are the window, out and in mark the letters leaving and entering on each slide, and the table on the right shows the update arithmetic.
flowchart TD
W["window hash hw"] --> EQ{"hw == hp ?"}
EQ -->|no| ROLL["roll: drop T[i], add T[i+m]"]
EQ -->|yes| CHK{"letters equal ?"}
CHK -->|yes| REP["report match at i"]
CHK -->|no| SP["spurious hit: ignore"]
REP --> ROLL
SP --> ROLL
ROLL --> W
Collisions, made intuitive
When can two different strings of the same length get the same hash? Their hash difference is
a polynomial in of degree at most that is not the zero polynomial (the strings differ somewhere). They collide exactly when is a root of that polynomial modulo . A nonzero polynomial of degree has at most roots modulo a prime. So if is chosen uniformly at random from :
For and , that is at most for one comparison: already decent, and in practice the hash behaves far better than this worst-case bound, close to a random function where the chance is .
The catch is that algorithms do not make one comparison. They make millions, and they often throw many hashes into a set and ask "do any two collide?". That is the birthday problem: in a room of 23 people the chance that some pair shares a birthday is over 50%, even though any particular pair matches with probability 1/365, because 23 people form 253 pairs. (The full derivation is in Probability for Engineers: the birthday paradox.) With hashes spread over values, the expected number of colliding pairs is about
Rule of thumb: collisions become likely once approaches . For , : a few tens of thousands of hashes in one set is enough to expect a collision. These numbers were computed with the formula above:
| Hashes in one set () | Modulus | Expected colliding pairs | P(at least one) |
|---|---|---|---|
| 0.05 | 4.9% | ||
| 5.0 | 99.3% | ||
| 500 | ≈ 100% | ||
| two moduli, | |||
| two moduli, | |||
Read the second row carefully. "Longest repeated substring" on a string of length puts window hashes into a set at each step of a binary search. With one modulus near , a false "repeat" is expected about five times per step. That is why a single hash is fine for Rabin–Karp (one pattern hash, compared against each window) but wrong for set-based problems at scale. Two moduli, or one modulus near , fix it.
Two kinds of comparisons
One-against-many (Rabin–Karp: each window against the single pattern hash): about expected false hits. Tiny even for . Many-against-many (a set of hashes, any pair may collide): about . Grows with the square. Size your modulus for this case.
Double hashing
Double hashing computes two independent hashes, with two different primes (and the same or different random bases), and treats the pair as the fingerprint. Two strings collide only if they collide under both. By the Chinese remainder theorem, a pair of residues modulo and carries the same information as one residue modulo , so the collision chance per pair drops to about . The cost is roughly twice the arithmetic.
An alternative is one hash modulo the Mersenne prime . Products of two 61-bit numbers need 122 bits, so you either use a 128-bit integer type (unsigned __int128 in GCC/Clang on 64-bit targets, Math.multiplyHigh in Java 9+) or split the operands into 31-bit halves. Reducing modulo needs no division: , then subtract once if needed. Many competitive programmers prefer this: one hash, -scale safety, fast.
Deeper: why the two halves of a double hash are "independent enough"
With a random base used for both moduli, a collision needs to be a root of the difference polynomial modulo and modulo . By the Chinese remainder theorem, is uniform when is uniform in , and the number of common roots is at most out of residues, so the bound is . In practice people draw uniformly in and use it for both, which is not exactly uniform modulo but behaves the same on every non-adversarial input. If you want the clean bound, draw two independent bases and ; then the events are independent and the bound is .
Anti-hash tests: when someone attacks your hash
The probability bounds above assume the base is random and secret. If the attacker knows your and (because they are hard-coded in your submission, or in an open-source library), the input is no longer random, and they can build collisions on purpose. On Codeforces, where other contestants can read your code and submit tests against it ("hacks"), this happens routinely.
Attack 1: (letting unsigned overflow do the modulus). Tempting, because it is free. It is broken for every base:
- If is even, , so only the last 64 characters affect the hash. Any two strings with the same last 64 characters collide.
- If is odd, the Thue–Morse string breaks it. Build $S_0 = $ "a", where swaps a and b. Then (length 1024) and its complement have the same hash modulo for every odd base. We checked this on 200 random odd 64-bit bases: all 200 collide at length 1024, while lengths 256 and 512 do not collide. (The reason: the hash difference factors as , and each factor is divisible by a growing power of 2.)
Attack 2: a fixed, known base and a prime near . The attacker just generates random strings, hashes them with your parameters, and waits for a birthday collision: about strings on average. One run of that search with , (a = 1, …, z = 26) found that "ynkgxyuyqr" and "lyvitiqmhs" both hash to 585947087, after 12,645 random strings. A test containing both breaks any code using those parameters.
Attack 3: tree attacks / lattice reduction against two fixed moduli. Even two fixed moduli near fall to smarter constructions; see the dacin21 survey in the sources. The defence is not "more moduli". The defence is randomness the attacker cannot see.
The defence, in one line: pick the base at random when the program starts (seeded from the clock or the OS), use a prime modulus (not ), and use two moduli or when you will compare many hashes.
This is not only a contest problem
In 2011, Alexander Klink and Julian Wälde showed ("Efficient Denial of Service Attacks on Web Application Platforms", 28C3) that most web frameworks hashed request parameters with fixed, public string hashes. An attacker could send a few hundred kilobytes of colliding parameter names and make a server's hash table degrade to a list, burning minutes of CPU per request. The industry fix was the same as ours: keyed, randomized hashing (Python's PYTHONHASHSEED, SipHash in Python, Rust and Ruby). See Hash Tables.
Choosing the modulus and the base
| Choice | Recommended | Why |
|---|---|---|
| Modulus | A prime: , , , or | Prime ⇒ the "at most roots" bound holds and every nonzero is invertible |
| Base | Random, uniform in (or above your alphabet size) | Random ⇒ the probability bounds apply; above the alphabet ⇒ no trivial "ak = ba" collisions |
| Character values | Character codes, or 1..σ | Never 0, or "a", "aa", "aaa" collide |
| Number of hashes | One for one-against-many; two (or ) for sets and many-against-many | Birthday bound, see the table above |
| Avoid | overflow; ; fixed in adversarial settings; even or tiny | Thue–Morse and birthday attacks |
Overflow rules per language, for just under :
- C++ / Java: both operands are below , so the product is below and fits in a 64-bit integer. Use
unsigned long long/long. In Java and C++,%of a negative number is negative, so write(a - b % M + M) % M. - Python: integers are unbounded,
%is always non-negative. Nothing to worry about except speed. - JavaScript / TypeScript: numbers are doubles, exact only up to . A product of two numbers near is about and silently loses precision. Either use a modulus below (weak),
BigInt(slow), or split the multiplication as in themulmodhelper below.
The ladder: brute force → better → optimal
Problem: answer queries "is equal to ?" on a string of length .
Rung 1: compare letters
Each query compares up to characters: per query, total in the worst case. No preprocessing. Correct and simple; too slow when and are both .
Rung 2: precompute every answer
Store an ID for every distinct substring (for example by inserting all substrings into a trie or a dictionary): substrings, to time and memory. Then each query is . Fast queries, but means substrings.
Rung 3: prefix hashes
preprocessing, memory, per query. Randomized: a wrong "equal" with probability about per query with double hashing. This is the sweet spot for almost every practical and contest problem.
Rung 4 (deterministic): suffix array + LCP + sparse table
Build a suffix array and the LCP array in , a sparse table over LCP in ; then "longest common prefix of suffixes and " is an range minimum, and the query is "LCP ". No probability at all, but several times more code and a larger constant.
| Rung | Method | Preprocessing | Per query | Memory | Exact? |
|---|---|---|---|---|---|
| 1 | Letter comparison | none | yes | ||
| 2 | Precompute all substrings | + | yes | ||
| 3 | Prefix hashes (double) | with probability | |||
| 4 | Suffix array + LCP + RMQ | yes |
For pattern search specifically, the ladder is: naive → Rabin–Karp expected → KMP or Z worst case. Rabin–Karp's niche is that it generalizes: many patterns of the same length, 2-D patterns, and fingerprints of streams.
Correctness
Claim 1: the substring formula is exact
By induction on , . Split the sum at : the terms with are , and the terms with are exactly the hash of . Subtract. Every step is an identity modulo , so equals the hash you would get by hashing the slice from scratch. No probability is involved yet.
Claim 2: equal strings always have equal hashes
The hash is a function of the characters only. Two equal slices produce the same sum term by term. So hashing never says "different" for equal strings: there are no false negatives, only (rare) false positives.
Claim 3: Rabin–Karp reports exactly the occurrences
The rolling update is Claim 1 applied to consecutive windows, so is always the true hash of the current window. Every real occurrence has (Claim 2) and passes the letter check, so it is reported. Every reported index passed the letter check, so it is a real occurrence. The probability only affects the running time (how many letter checks run), never the output.
Claim 4: the collision bound
Shown above: for distinct equal-length strings, a collision means is a root of a nonzero polynomial of degree over the field , which has at most roots. With uniform, . A union bound over all pairs compared gives the total failure probability. For strings of different lengths, compare lengths first (or put the length in the key); polynomial hashes of different lengths are not comparable through this bound.
Hashing-based algorithms with binary search
"Longest repeated substring" binary searches on the length . The predicate "some substring of length occurs twice" is monotone: if a length- substring occurs twice, so do its length- prefixes. So the predicate is true for and false after, and binary search on the answer finds . The hash can only err by reporting a false repeat (Claim 2), which would make the answer too long; double hashing makes that event negligible, and you can remove it entirely by verifying the two candidate substrings letter by letter.
Complexity
| Operation | Time | Space |
|---|---|---|
| Build prefix hashes and powers | ||
| Hash of any substring | — | |
| Rabin–Karp, expected | extra | |
| Rabin–Karp, worst case | extra | |
| Longest repeated substring | expected | |
| Count distinct substrings | expected | per length |
Two notes on Rabin–Karp's cost. First, the expected number of spurious hits is at most by Claim 4, each costing , which is negligible for . Second, real matches also cost each to verify. On $T = $ "aaaa…a" and $P = $ "aa…a", every window matches and Rabin–Karp spends verifying. That is why its worst case is even with a perfect hash. If you only need a count, or if you accept a risk, skip verification with double hashing and the time is always. KMP and Z give deterministically.
The constant factor: each step is one or two multiplications and modulo operations. Modulo by a constant prime compiles to multiply-and-shift in C++ and Java, so a double hash costs a few nanoseconds per character. In Python, a double prefix hash over characters took about 0.4 seconds in our test, and a million get calls about 0.3 seconds more; use built-in slicing comparisons where possible, they run in C.
Implementation
StringHash (double hash, random base, substring hashes), Rabin–Karp with a configurable modulus (the tests run it with to prove the letter check rejects the spurious hit at index 2), longest repeated substring by binary search, and distinct substrings. Every version was compiled and run with the same assertions; the Python version was also cross-checked against brute force on 2,000 random strings over {a, b}, including with modulus 7 to force many collisions.
import random
M1, M2 = 1_000_000_007, 1_000_000_009
class StringHash:
"""Double polynomial hash of s. get(l, r) is the hash of s[l:r] in O(1)."""
def __init__(self, s: str, base: int | None = None) -> None:
self.base = base if base is not None else random.randrange(256, M1)
n = len(s)
self.h1, self.h2 = [0] * (n + 1), [0] * (n + 1)
self.p1, self.p2 = [1] * (n + 1), [1] * (n + 1)
for i, ch in enumerate(s):
c = ord(ch)
self.h1[i + 1] = (self.h1[i] * self.base + c) % M1
self.h2[i + 1] = (self.h2[i] * self.base + c) % M2
self.p1[i + 1] = self.p1[i] * self.base % M1
self.p2[i + 1] = self.p2[i] * self.base % M2
def get(self, l: int, r: int) -> tuple[int, int]:
"""Hash of the half-open slice s[l:r]."""
return ((self.h1[r] - self.h1[l] * self.p1[r - l]) % M1,
(self.h2[r] - self.h2[l] * self.p2[r - l]) % M2)
def rabin_karp(text: str, pattern: str, mod: int = M1, base: int | None = None) -> list[int]:
"""All start indices of pattern in text. Rolling hash + verification, so never wrong."""
n, m = len(text), len(pattern)
if m == 0 or m > n:
return []
b = base if base is not None else random.randrange(256, mod)
top = pow(b, m - 1, mod) # weight of the window's leftmost character
hp = hw = 0
for i in range(m):
hp = (hp * b + ord(pattern[i])) % mod
hw = (hw * b + ord(text[i])) % mod
found = []
for i in range(n - m + 1):
if hw == hp and text[i:i + m] == pattern: # equal hashes are only a hint
found.append(i)
if i + m < n: # slide: drop text[i], add text[i+m]
hw = ((hw - ord(text[i]) * top) * b + ord(text[i + m])) % mod
return found
def longest_repeated_substring(s: str) -> str:
"""Longest substring occurring at least twice (overlaps allowed). O(n log n) expected."""
sh = StringHash(s)
def repeat_start(length: int) -> int:
seen = set()
for i in range(len(s) - length + 1):
h = sh.get(i, i + length)
if h in seen:
return i
seen.add(h)
return -1
lo, hi, start = 0, len(s) - 1, 0 # length lo always repeats (lo = 0: empty string)
while lo < hi:
mid = (lo + hi + 1) // 2
i = repeat_start(mid)
if i >= 0:
lo, start = mid, i
else:
hi = mid - 1
return s[start:start + lo]
def count_distinct_substrings(s: str) -> int:
"""Number of distinct non-empty substrings. O(n^2) expected."""
sh = StringHash(s)
n = len(s)
return sum(len({sh.get(i, i + L) for i in range(n - L + 1)}) for L in range(1, n + 1))
if __name__ == "__main__":
sh = StringHash("banana", base=31)
assert sh.get(1, 4) == sh.get(3, 6) # "ana" == "ana"
assert sh.get(0, 2) != sh.get(2, 4) # "ba" != "na"
assert rabin_karp("abracadabra", "abra") == [0, 7]
assert rabin_karp("abracadabra", "abra", mod=11, base=31) == [0, 7] # spurious hit at 2 rejected
assert rabin_karp("aaaaa", "aa") == [0, 1, 2, 3]
assert rabin_karp("abc", "abcd") == [] and rabin_karp("abc", "") == []
assert longest_repeated_substring("banana") == "ana"
assert longest_repeated_substring("abcd") == ""
assert longest_repeated_substring("aaaaa") == "aaaa"
assert longest_repeated_substring("") == ""
assert count_distinct_substrings("abab") == 7
assert count_distinct_substrings("aaa") == 3
assert count_distinct_substrings("banana") == 15
print("all tests passed")
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.concurrent.ThreadLocalRandom;
public class Hashing {
static final long M1 = 1_000_000_007L, M2 = 1_000_000_009L;
/** Double polynomial hash of s. get(l, r) is the hash of s.substring(l, r) in O(1). */
static final class StringHash {
final long base;
final long[] h1, h2, p1, p2;
StringHash(String s) { this(s, ThreadLocalRandom.current().nextLong(256, M1)); }
StringHash(String s, long base) {
this.base = base;
int n = s.length();
h1 = new long[n + 1]; h2 = new long[n + 1];
p1 = new long[n + 1]; p2 = new long[n + 1];
p1[0] = p2[0] = 1;
for (int i = 0; i < n; i++) {
long c = s.charAt(i);
h1[i + 1] = (h1[i] * base + c) % M1;
h2[i + 1] = (h2[i] * base + c) % M2;
p1[i + 1] = p1[i] * base % M1;
p2[i + 1] = p2[i] * base % M2;
}
}
/** Both hashes packed into one long (each is below 2^30). */
long get(int l, int r) {
long a = ((h1[r] - h1[l] * p1[r - l]) % M1 + M1) % M1;
long b = ((h2[r] - h2[l] * p2[r - l]) % M2 + M2) % M2;
return a << 32 | b;
}
}
/** All start indices of pattern in text. Rolling hash + verification, so never wrong. */
static List<Integer> rabinKarp(String text, String pattern, long mod, long base) {
int n = text.length(), m = pattern.length();
List<Integer> found = new ArrayList<>();
if (m == 0 || m > n) return found;
long top = 1; // base^(m-1): weight of the leftmost char
for (int i = 0; i < m - 1; i++) top = top * base % mod;
long hp = 0, hw = 0;
for (int i = 0; i < m; i++) {
hp = (hp * base + pattern.charAt(i)) % mod;
hw = (hw * base + text.charAt(i)) % mod;
}
for (int i = 0; i + m <= n; i++) {
if (hw == hp && text.regionMatches(i, pattern, 0, m)) found.add(i);
if (i + m < n) {
long out = text.charAt(i) * top % mod;
hw = ((hw - out + mod) % mod * base + text.charAt(i + m)) % mod;
}
}
return found;
}
static List<Integer> rabinKarp(String text, String pattern) {
return rabinKarp(text, pattern, M1, ThreadLocalRandom.current().nextLong(256, M1));
}
/** Longest substring occurring at least twice (overlaps allowed). */
static String longestRepeatedSubstring(String s) {
StringHash sh = new StringHash(s);
int lo = 0, hi = s.length() - 1, start = 0;
while (lo < hi) {
int mid = (lo + hi + 1) / 2, i = repeatStart(s, sh, mid);
if (i >= 0) { lo = mid; start = i; } else hi = mid - 1;
}
return s.substring(start, start + lo);
}
private static int repeatStart(String s, StringHash sh, int len) {
Set<Long> seen = new HashSet<>();
for (int i = 0; i + len <= s.length(); i++)
if (!seen.add(sh.get(i, i + len))) return i;
return -1;
}
/** Number of distinct non-empty substrings, O(n^2) expected. */
static long countDistinctSubstrings(String s) {
StringHash sh = new StringHash(s);
int n = s.length();
long total = 0;
for (int len = 1; len <= n; len++) {
Set<Long> seen = new HashSet<>();
for (int i = 0; i + len <= n; i++) seen.add(sh.get(i, i + len));
total += seen.size();
}
return total;
}
static void check(boolean ok, String what) { if (!ok) throw new AssertionError(what); }
public static void main(String[] args) {
StringHash sh = new StringHash("banana", 31);
check(sh.get(1, 4) == sh.get(3, 6), "ana == ana");
check(sh.get(0, 2) != sh.get(2, 4), "ba != na");
check(rabinKarp("abracadabra", "abra").equals(List.of(0, 7)), "rk");
check(rabinKarp("abracadabra", "abra", 11, 31).equals(List.of(0, 7)), "rk spurious");
check(rabinKarp("aaaaa", "aa").equals(List.of(0, 1, 2, 3)), "rk overlap");
check(rabinKarp("abc", "abcd").isEmpty() && rabinKarp("abc", "").isEmpty(), "rk edge");
check(longestRepeatedSubstring("banana").equals("ana"), "lrs banana");
check(longestRepeatedSubstring("abcd").equals(""), "lrs abcd");
check(longestRepeatedSubstring("aaaaa").equals("aaaa"), "lrs aaaaa");
check(longestRepeatedSubstring("").equals(""), "lrs empty");
check(countDistinctSubstrings("abab") == 7, "distinct abab");
check(countDistinctSubstrings("aaa") == 3, "distinct aaa");
check(countDistinctSubstrings("banana") == 15, "distinct banana");
System.out.println("all tests passed");
}
}
#include <cassert>
#include <chrono>
#include <iostream>
#include <random>
#include <string>
#include <unordered_set>
#include <vector>
using namespace std;
typedef unsigned long long ull;
const ull M1 = 1000000007ULL, M2 = 1000000009ULL;
ull randomBase(ull mod) {
static mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
return uniform_int_distribution<ull>(256, mod - 1)(rng);
}
// Double polynomial hash of s. get(l, r) is the hash of s.substr(l, r - l) in O(1).
struct StringHash {
vector<ull> h1, h2, p1, p2;
explicit StringHash(const string& s, ull base = randomBase(M1))
: h1(s.size() + 1, 0), h2(s.size() + 1, 0), p1(s.size() + 1, 1), p2(s.size() + 1, 1) {
for (size_t i = 0; i < s.size(); i++) {
ull c = (unsigned char)s[i];
h1[i + 1] = (h1[i] * base + c) % M1;
h2[i + 1] = (h2[i] * base + c) % M2;
p1[i + 1] = p1[i] * base % M1;
p2[i + 1] = p2[i] * base % M2;
}
}
// Both hashes packed into one 64-bit key (each is below 2^30).
ull get(size_t l, size_t r) const {
ull a = (h1[r] + M1 - h1[l] * p1[r - l] % M1) % M1;
ull b = (h2[r] + M2 - h2[l] * p2[r - l] % M2) % M2;
return a << 32 | b;
}
};
// All start indices of pattern in text. Rolling hash + verification, so never wrong.
vector<int> rabinKarp(const string& text, const string& pattern, ull mod = M1, ull base = 0) {
size_t n = text.size(), m = pattern.size();
vector<int> found;
if (m == 0 || m > n) return found;
if (base == 0) base = randomBase(mod);
ull top = 1; // base^(m-1): weight of the leftmost char
for (size_t i = 0; i + 1 < m; i++) top = top * base % mod;
ull hp = 0, hw = 0;
for (size_t i = 0; i < m; i++) {
hp = (hp * base + (unsigned char)pattern[i]) % mod;
hw = (hw * base + (unsigned char)text[i]) % mod;
}
for (size_t i = 0; i + m <= n; i++) {
if (hw == hp && text.compare(i, m, pattern) == 0) found.push_back((int)i);
if (i + m < n) {
ull out = (unsigned char)text[i] * top % mod;
hw = ((hw + mod - out) % mod * base + (unsigned char)text[i + m]) % mod;
}
}
return found;
}
// Longest substring occurring at least twice (overlaps allowed).
string longestRepeatedSubstring(const string& s) {
StringHash sh(s);
auto repeatStart = [&](size_t len) -> long long {
unordered_set<ull> seen;
for (size_t i = 0; i + len <= s.size(); i++)
if (!seen.insert(sh.get(i, i + len)).second) return (long long)i;
return -1;
};
long long lo = 0, hi = (long long)s.size() - 1, start = 0;
while (lo < hi) {
long long mid = (lo + hi + 1) / 2, i = repeatStart((size_t)mid);
if (i >= 0) { lo = mid; start = i; } else hi = mid - 1;
}
return s.substr((size_t)start, (size_t)lo);
}
// Number of distinct non-empty substrings, O(n^2) expected.
long long countDistinctSubstrings(const string& s) {
StringHash sh(s);
long long total = 0;
for (size_t len = 1; len <= s.size(); len++) {
unordered_set<ull> seen;
for (size_t i = 0; i + len <= s.size(); i++) seen.insert(sh.get(i, i + len));
total += (long long)seen.size();
}
return total;
}
int main() {
StringHash sh("banana", 31);
assert(sh.get(1, 4) == sh.get(3, 6)); // "ana" == "ana"
assert(sh.get(0, 2) != sh.get(2, 4)); // "ba" != "na"
assert(rabinKarp("abracadabra", "abra") == vector<int>({0, 7}));
assert(rabinKarp("abracadabra", "abra", 11, 31) == vector<int>({0, 7})); // spurious hit rejected
assert(rabinKarp("aaaaa", "aa") == vector<int>({0, 1, 2, 3}));
assert(rabinKarp("abc", "abcd").empty() && rabinKarp("abc", "").empty());
assert(longestRepeatedSubstring("banana") == "ana");
assert(longestRepeatedSubstring("abcd") == "");
assert(longestRepeatedSubstring("aaaaa") == "aaaa");
assert(longestRepeatedSubstring("") == "");
assert(countDistinctSubstrings("abab") == 7);
assert(countDistinctSubstrings("aaa") == 3);
assert(countDistinctSubstrings("banana") == 15);
cout << "all tests passed\n";
}
const M1 = 1_000_000_007;
const M2 = 1_000_000_009;
// (a * b) % m without leaving the exact-integer range of doubles (2^53):
// split b into 16-bit halves so every partial product stays below 2^47.
function mulmod(a: number, b: number, m: number): number {
const hi = (a * Math.floor(b / 65536)) % m;
return (hi * 65536 + a * (b % 65536)) % m;
}
function randomBase(mod: number): number {
return 256 + Math.floor(Math.random() * (mod - 256));
}
/** Double polynomial hash of s. get(l, r) is the hash of s.slice(l, r) in O(1). */
class StringHash {
private readonly h1: number[];
private readonly h2: number[];
private readonly p1: number[];
private readonly p2: number[];
constructor(s: string, readonly base: number = randomBase(M1)) {
const n = s.length;
this.h1 = new Array<number>(n + 1).fill(0);
this.h2 = new Array<number>(n + 1).fill(0);
this.p1 = new Array<number>(n + 1).fill(1);
this.p2 = new Array<number>(n + 1).fill(1);
for (let i = 0; i < n; i++) {
const c = s.charCodeAt(i);
this.h1[i + 1] = (mulmod(this.h1[i], base, M1) + c) % M1;
this.h2[i + 1] = (mulmod(this.h2[i], base, M2) + c) % M2;
this.p1[i + 1] = mulmod(this.p1[i], base, M1);
this.p2[i + 1] = mulmod(this.p2[i], base, M2);
}
}
/** A string key holding both hashes (two 30-bit numbers do not fit one double exactly). */
get(l: number, r: number): string {
const a = (this.h1[r] - mulmod(this.h1[l], this.p1[r - l], M1) + M1) % M1;
const b = (this.h2[r] - mulmod(this.h2[l], this.p2[r - l], M2) + M2) % M2;
return `${a}:${b}`;
}
}
/** All start indices of pattern in text. Rolling hash + verification, so never wrong. */
function rabinKarp(text: string, pattern: string, mod = M1, base = randomBase(M1)): number[] {
const n = text.length;
const m = pattern.length;
const found: number[] = [];
if (m === 0 || m > n) return found;
let top = 1; // base^(m-1): weight of the leftmost character
for (let i = 0; i < m - 1; i++) top = mulmod(top, base, mod);
let hp = 0;
let hw = 0;
for (let i = 0; i < m; i++) {
hp = (mulmod(hp, base, mod) + pattern.charCodeAt(i)) % mod;
hw = (mulmod(hw, base, mod) + text.charCodeAt(i)) % mod;
}
for (let i = 0; i + m <= n; i++) {
if (hw === hp && text.startsWith(pattern, i)) found.push(i);
if (i + m < n) {
const out = mulmod(text.charCodeAt(i), top, mod);
hw = (mulmod((hw - out + mod) % mod, base, mod) + text.charCodeAt(i + m)) % mod;
}
}
return found;
}
/** Longest substring occurring at least twice (overlaps allowed). */
function longestRepeatedSubstring(s: string): string {
const sh = new StringHash(s);
const repeatStart = (len: number): number => {
const seen = new Set<string>();
for (let i = 0; i + len <= s.length; i++) {
const h = sh.get(i, i + len);
if (seen.has(h)) return i;
seen.add(h);
}
return -1;
};
let lo = 0;
let hi = s.length - 1;
let start = 0;
while (lo < hi) {
const mid = Math.floor((lo + hi + 1) / 2);
const i = repeatStart(mid);
if (i >= 0) {
lo = mid;
start = i;
} else {
hi = mid - 1;
}
}
return s.slice(start, start + lo);
}
/** Number of distinct non-empty substrings, O(n^2) expected. */
function countDistinctSubstrings(s: string): number {
const sh = new StringHash(s);
let total = 0;
for (let len = 1; len <= s.length; len++) {
const seen = new Set<string>();
for (let i = 0; i + len <= s.length; i++) seen.add(sh.get(i, i + len));
total += seen.size;
}
return total;
}
function check(ok: boolean, what: string): void {
if (!ok) throw new Error(`check failed: ${what}`);
}
const same = (a: number[], b: number[]) => a.length === b.length && a.every((x, i) => x === b[i]);
const sh = new StringHash("banana", 31);
check(sh.get(1, 4) === sh.get(3, 6), "ana == ana");
check(sh.get(0, 2) !== sh.get(2, 4), "ba != na");
check(same(rabinKarp("abracadabra", "abra"), [0, 7]), "rk");
check(same(rabinKarp("abracadabra", "abra", 11, 31), [0, 7]), "rk spurious");
check(same(rabinKarp("aaaaa", "aa"), [0, 1, 2, 3]), "rk overlap");
check(rabinKarp("abc", "abcd").length === 0 && rabinKarp("abc", "").length === 0, "rk edge");
check(longestRepeatedSubstring("banana") === "ana", "lrs banana");
check(longestRepeatedSubstring("abcd") === "", "lrs abcd");
check(longestRepeatedSubstring("aaaaa") === "aaaa", "lrs aaaaa");
check(longestRepeatedSubstring("") === "", "lrs empty");
check(countDistinctSubstrings("abab") === 7, "distinct abab");
check(countDistinctSubstrings("aaa") === 3, "distinct aaa");
check(countDistinctSubstrings("banana") === 15, "distinct banana");
check(mulmod(999_999_999, 999_999_999, M1) === Number((999_999_999n * 999_999_999n) % 1_000_000_007n), "mulmod");
console.log("all tests passed");
Notes on the four versions. Java and C++ pack the two 30-bit hashes into one 64-bit key, which makes HashSet<Long> and unordered_set<ull> cheap. TypeScript cannot pack two 30-bit numbers into one double exactly (that needs 60 bits; doubles hold 53), so it uses a string key; a faster alternative is a Map<number, Set<number>> keyed by the first hash. The TypeScript mulmod is the part people forget: without it, h * base for h near exceeds and the hash silently becomes wrong (not just weaker: equal substrings can get different hashes, because the rounding depends on the prefix).
Applications
Longest repeated substring: binary search + hashing
Problem. Find the longest substring that occurs at least twice in (the occurrences may overlap). For "banana" it is "ana" (at 1 and 3).
Idea. Guess a length . Checking "does some length- substring repeat?" is easy with hashing: slide over all windows, put each hash into a set, and stop at the first duplicate. That check is expected. The answer to the check is "yes" for every up to the true answer and "no" above it (monotone, as proved in Correctness), so binary search finds with checks: total.
Worked by hand on "banana" (, search ):
| Step | lo | hi | mid | Windows of length mid | First repeat? | Result |
|---|---|---|---|---|---|---|
| 1 | 0 | 5 | 3 | ban, ana, nan, ana | yes, at 3 | lo = 3, start = 3 |
| 2 | 3 | 5 | 4 | bana, anan, nana | no | hi = 3 |
| 3 | 3 | 3 | — | — | — | stop: "ana" |
This is LeetCode 1044 "Longest Duplicate Substring", where is up to , so each check puts up to hashes in a set. With a single modulus near , the birthday table predicts roughly a 35% chance of at least one false collision per check; over 15 checks, wrong answers are likely. With double hashing it is safe. The suffix-array solution (Suffix Arrays) answers the same question deterministically: the answer is the maximum of the LCP array.
Counting distinct substrings
Problem. How many different non-empty substrings does have? For "abab": a, b, ab, ba, aba, bab, abab = 7.
Idea. For each length from 1 to , put the hashes of all windows into a set; the set's size is the number of distinct substrings of that length. Sum over . That is expected time, fine for up to a few thousand. Using one set per length means substrings of different lengths are never compared, which avoids the "different lengths" caveat in Claim 4.
| Windows of "abab" | Distinct | |
|---|---|---|
| 1 | a, b, a, b | 2 |
| 2 | ab, ba, ab | 2 |
| 3 | aba, bab | 2 |
| 4 | abab | 1 |
| Total | 7 |
For large , the right tool is a suffix array () or a suffix automaton (sum of len[v] - len[link[v]]), both near-linear.
More things hashing does in a few lines
- Longest common substring of two strings: binary search on ; put the length- hashes of the first string in a set, probe with the second. .
- Palindrome queries: hash and its reverse; is a palindrome iff its forward hash equals the hash of the mirrored range in the reverse.
- Longest common prefix of two suffixes / lexicographic comparison: binary search the LCP with hash comparisons, then compare the next character. per comparison, which lets you sort suffixes in with a normal sort.
- Borders and periods: has border length iff . (KMP's prefix function gives all of them deterministically.)
- Cyclic rotations: is a rotation of iff occurs in .
- 2-D pattern matching: hash each row's windows, then run a rolling hash down the columns of row hashes (Bird–Baker is the deterministic alternative).
Real-world uses
- rsync. Andrew Tridgell and Paul Mackerras's rsync algorithm (1996) finds which blocks of a file the other side already has by sliding a cheap rolling checksum over the file one byte at a time and confirming candidate matches with a strong hash. Exactly Rabin–Karp's "cheap hint, then verify" structure.
- Deduplicating storage and backups. Content-defined chunking cuts a file wherever a rolling hash of the last 48 or so bytes hits a chosen bit pattern, so an insertion only changes the chunks around it. Introduced by the Low-Bandwidth File System (Muthitacharoen, Chen, Mazières, SOSP 2001) using Rabin fingerprints; used by backup tools such as restic and Borg.
- Plagiarism detection. MOSS uses winnowing (Schleimer, Wilkerson, Aiken, SIGMOD 2003): hash every -gram of a document with a rolling hash and keep the minimum in each window as the document's fingerprint set.
- Bioinformatics. Read aligners and genome assemblers index -mers by hash; the minimizer idea (keep the smallest -mer hash in each window) is a central technique of tools such as minimap2.
- Hash tables everywhere. Language runtimes hash strings for dictionaries; after the 2011 hash-flooding disclosure, they moved to keyed hashes such as SipHash, the same "secret random parameter" defence as our random base.
- Network and security tooling. Some intrusion-detection systems and spam filters prefilter traffic with rolling hashes of fixed-length windows before running exact matchers such as Aho–Corasick.
Pitfalls & edge cases
- Mapping a character to 0. "a", "aa", "aaa" all hash to 0. Use codes .
- Base not above the alphabet. With and letters up to 26, "ak" and "ba" collide by arithmetic, not by bad luck.
- Fixed base in an adversarial setting. Hard-coded , is broken by a 40,000-string birthday search. Randomize at run time.
- via overflow. Broken by Thue–Morse for any odd base and trivially for any even base. Use a prime.
- Negative remainders. In Java, C++, C# and JavaScript,
(a - b) % Mcan be negative. Add before taking the remainder. - Overflow. In C++/Java keep both factors below so the product fits in 64 bits. In JavaScript, products above lose precision: use
mulmod,BigInt, or small moduli. - Comparing hashes of different lengths. Two strings of different lengths can share a hash in a way the bound does not cover. Compare lengths first, or key sets by .
- Forgetting to verify in Rabin–Karp (when correctness matters) or verifying on every real match when there are of them (when speed matters). Decide which you need.
- Single hash in a big set. Fine for one-against-many; for hashes in a set, a single -scale hash collides with high probability. Double hash.
- Off-by-one in . Keep
hof size , usep[r - l], and test on the empty substring and the whole string. - Unicode.
charCodeAtin JavaScript andcharAtin Java return UTF-16 code units, not code points; Python'sordreturns code points. Hashes still work (consistently), but substring boundaries may split a surrogate pair. - Speed in Python. A Python loop over characters with two moduli is slow. Precompute with one pass and avoid per-query object creation; compare slices directly when the slices are short.
Variations
- Mersenne-prime hashing modulo : one hash with -scale safety and division-free reduction.
- Rabin fingerprints over GF(2). Treat the bit string as a polynomial over the two-element field and reduce modulo a random irreducible polynomial of degree 64. Computed with shifts and XORs (table-driven, like CRC). This is what LBFS and many deduplication systems use.
- Multiset (anagram) hashing. Assign each character a random 64-bit value and add them (or multiply over a random ): order-independent, so anagrams collide on purpose. Useful for "find all anagrams of in " with a sliding window.
- Hashing with updates. Store in a Fenwick tree; a point update changes one term and a range hash is a prefix-sum difference divided by (or multiplied to align) a power of . Supports "change a character, then ask whether a range is a palindrome".
- Tree and graph hashing. Hash rooted trees bottom-up from sorted child hashes (or AHU canonical forms) to test isomorphism; see tree problem patterns.
- 2-D rolling hash. Roll along rows, then along columns of row hashes, to match a pattern in an grid in expected.
- Universal hashing. The polynomial hash with a random base is a classic almost-universal family; this is the theory behind the bounds here and behind randomized hash tables (Randomized Algorithms).
Practice ladder
Each problem is described in my own words; follow the link for the full statement.
1. Find the Index of the First Occurrence in a String (LeetCode 28) — First position where a short string appears inside a longer one. Teaches Rabin–Karp end to end.
Hint
Roll a window of the needle's length; on a hash match, compare letters; return the first confirmed index, or −1.
2. String Matching (CSES 1753) — Count occurrences of a pattern in a text of length up to . Teaches the verification cost trap.
Hint
With text "aaaa…" and pattern "aaa…", verifying every match is . Either count matches by hash equality with a double hash (no verification), or use KMP/Z.
3. Repeated DNA Sequences (LeetCode 187) — Every 10-letter DNA window that appears more than once. Teaches exact rolling hashes when the window is short.
Hint
Four letters fit in 2 bits, so 10 letters fit in 20 bits: the rolling "hash" is the window itself, packed, with no collisions at all.
Solution
def find_repeated_dna_sequences(s: str) -> list[str]:
code = {"A": 0, "C": 1, "G": 2, "T": 3}
seen, out, x = set(), set(), 0
for i, ch in enumerate(s):
x = ((x << 2) | code[ch]) & 0xFFFFF # last 10 letters = 20 bits, an exact (collision-free) hash
if i >= 9:
if x in seen:
out.add(s[i - 9:i + 1])
seen.add(x)
return sorted(out)
Shift in 2 bits per letter and mask to 20 bits: the mask is "drop the letter leaving the window". time, and correct with certainty because the encoding is injective.
4. Longest Happy Prefix (LeetCode 1392) — Longest proper prefix that is also a suffix. Teaches prefix-versus-suffix hash comparison.
Hint
For down to 1, compare hash with hash; the first equal pair is the answer. (KMP's prefix function gives the same in deterministically: it is .)
Solution
def longest_prefix(s: str) -> str:
sh = StringHash(s) # the class from the Implementation section
n = len(s)
for length in range(n - 1, 0, -1):
if sh.get(0, length) == sh.get(n - length, n):
return s[:length]
return ""
hash comparisons. "level" gives "l"; "ababab" gives "abab".
5. Finding Borders (CSES 1732) — List every border length of a string. Same check as problem 4, but report all lengths.
Hint
Loop and print each with equal prefix and suffix hashes. Use a random base anyway: fixed, well-known parameters are exactly what anti-hash tests target.
6. Shortest Palindrome (LeetCode 214) — Add the fewest characters in front of a string to make it a palindrome. Teaches forward and reverse rolling hashes in one pass.
Hint
Find the longest prefix that is a palindrome. Scan left to right maintaining the forward hash of the prefix and the hash of the reversed prefix (new character added at the high end: rev += v * B^i); whenever they are equal, the prefix is (with high probability) a palindrome.
7. Maximum Length of Repeated Subarray (LeetCode 718) — Longest contiguous block common to two integer arrays. Teaches binary search + hashing across two sequences.
Hint
Binary search ; hash every length- window of the first array into a set, probe with the second. Values go up to 100, so use a base above 100. The DP is the deterministic alternative.
8. Distinct Echo Substrings (LeetCode 1316) — Count distinct substrings of the form (some string written twice). Teaches half-versus-half checks and deduplicating by hash.
Hint
For each half-length and start , compare hash with hash; store of the matches in a set.
Solution
def distinct_echo_substrings(text: str) -> int:
sh = StringHash(text)
n = len(text)
found = set()
for half in range(1, n // 2 + 1):
for i in range(n - 2 * half + 1):
if sh.get(i, i + half) == sh.get(i + half, i + 2 * half):
found.add((half, sh.get(i, i + half)))
return len(found)
expected. "abcabcabc" has 3 ("abcabc", "bcabca", "cabcab"), "leetcodeleetcode" has 2 ("ee", "leetcodeleetcode").
9. Longest Duplicate Substring (LeetCode 1044) — The longest substring that appears at least twice, string length up to . Teaches the binary-search pattern and why a single hash fails at scale.
Hint
The longest_repeated_substring function in the Implementation section is a full solution. With one modulus near , expect wrong answers from birthday collisions; double hash.
10. Number of Distinct Substrings in a String (LeetCode 1698, premium) — Count distinct substrings, . Teaches per-length hash sets.
Hint
count_distinct_substrings above, . Follow-up: do it in or with a suffix automaton or suffix array.
11. Compress Words (Codeforces 1200E) — Merge words left to right, overlapping each new word with the longest possible suffix of the result. Teaches comparing a suffix of a growing string with a prefix of a new one.
Hint
Keep a prefix hash of the result as it grows. For each new word of length , only the last characters of the result matter; test overlaps from down. Total work is the sum of word lengths. Random base is essential: this problem is a known anti-hash target.
12. Palindrome Queries (CSES 2420) — Point updates to a string mixed with "is this range a palindrome?" queries. Teaches hashing with a Fenwick tree.
Hint
Store in one Fenwick tree and in another. A range's forward and backward sums must be aligned by multiplying the one with the smaller exponent offset by the right power of before comparing.
13. Longest Common Subpath (LeetCode 1923) — Longest contiguous city sequence shared by every friend's path. Teaches binary search with set intersection across many sequences, and is notorious for breaking single and fixed hashes.
Hint
Binary search ; for each path build the set of its length- window hashes and intersect. Use double hashing with random bases; total work .
Common mistakes & interview follow-ups
"What is the probability that your hash gives a wrong answer?" For one comparison of two different length- strings with a random base: at most . For a set of hashes: about expected collisions (birthday). Then state your parameters: "two primes near , so about ."
"Why a prime modulus?" So is a field: a nonzero polynomial of degree has at most roots, which is the collision bound. With the bound fails, and Thue–Morse strings collide for every odd base.
"Can you make Rabin–Karp deterministic?" It is already always correct if you verify; only the time is random. For a deterministic time bound, use KMP or Z.
"How do you handle many patterns?" If they all have the same length, put their hashes in a set and roll one window: expected. For different lengths, either one rolling hash per distinct length, or Aho–Corasick.
"Why not just use the language's built-in string hash?" It hashes a whole string in ; it cannot give you the hash of a substring in , and it cannot roll.
"How would you compare two substrings lexicographically in ?" Binary search the length of their common prefix with hash comparisons, then compare the first differing character.
Mistakes interviewers watch for: character value 0; base below the alphabet size; negative %; 64-bit overflow in the multiplication; JavaScript precision loss above ; forgetting verification and calling it "exact"; one hash in a large set; comparing hashes of substrings of different lengths.
Quick quiz
1. With , a = 1, b = 2, compute the polynomial hash of "ab" (no modulus needed), and explain why giving a the value 0 would be a mistake.
Answer
. With a = 0, "ab" and "b" would both hash to 2: leading zeros vanish, so any strings that differ only by leading a's collide.
2. In the "banana" table, h[3] = 1967 and h[6] = 58600293. Using p[3] = 29791, what is the hash of , and which substring is it?
Answer
, the hash of "ana", equal to hash.
3. You put substring hashes into a set using one modulus . About how many false collisions should you expect?
Answer
. Use two moduli (expected ) or .
4. Why is Rabin–Karp's worst case even if the hash function never produces a spurious hit?
Answer
Real matches must be verified too. On , , all windows match and each check costs .
5. Your C++ solution uses unsigned long long overflow as the modulus and a random odd base. Is it safe against a hacker who can read your code?
Answer
No. The Thue–Morse string of length 1024 and its complement collide modulo for every odd base, random or not (an even base is even worse: only the last 64 characters count). Use a prime modulus with a random base.
Further reading / sources
- Richard M. Karp and Michael O. Rabin, "Efficient randomized pattern-matching algorithms", IBM Journal of Research and Development 31(2), 1987 — the original Rabin–Karp paper.
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms, 4th ed., §32.2 "The Rabin-Karp algorithm".
- Robert Sedgewick and Kevin Wayne, Algorithms, 4th ed., §5.3 (Rabin–Karp fingerprint search, with the Monte Carlo / Las Vegas distinction).
- cp-algorithms: String Hashing and Rabin-Karp.
- dacin21, "On the mathematics behind rolling hashes and anti-hash tests", Codeforces, 2018 — Thue–Morse, tree attacks, lattice reduction and the case for random bases.
- Andrew Tridgell and Paul Mackerras, "The rsync algorithm", Technical Report TR-CS-96-05, Australian National University, 1996.
- Athicha Muthitacharoen, Benjie Chen, David Mazières, "A Low-Bandwidth Network File System", SOSP 2001 (content-defined chunking with Rabin fingerprints).
- Saul Schleimer, Daniel S. Wilkerson, Alex Aiken, "Winnowing: Local Algorithms for Document Fingerprinting", SIGMOD 2003.
- Alexander Klink and Julian Wälde, "Efficient Denial of Service Attacks on Web Application Platforms", 28th Chaos Communication Congress, 2011.
- The numeric claims on this page (prefix tables, the trace, the birthday table, the Thue–Morse check over 200 random odd bases, and the 12,645-string birthday collision) were produced by running scripts against the code above; the visualizer is generated by
scripts/traces/rabin_karp.py.
Previous lesson: String Algorithms (Module 7 Overview) · Next lesson: KMP & the Prefix Function
Related: Hash Tables · Prefix Sums · Sliding Window · Binary Search · Probability for Engineers · Z-Algorithm · Course home