String hashing

String hashing turns a string into a number, its hash, so that two strings can be compared with one comparison of numbers instead of letter by letter. Prepared once, it gives the hash of every substring of a string in $O(1)$, so substrings can be compared and searched for just as fast. Two different strings can, rarely, get the same hash; to find one pattern in a text with an answer that is always exact, the prefix function or the Z-function is the closer tool.

Explanation

Comparing two strings letter by letter takes as many steps as they are long, and that adds up when a program compares many strings. If every string had one number, and equal strings had equal numbers, each comparison would be one step.

Give each letter a code: a = 1, b = 2, c = 3. A first idea for the number of a string is the sum of its codes. The string abcabcbac is made of abc, abc and bac, at positions 1–3, 4–6 and 7–9, and all three get the sum 6.

Fig. 1. The sum gets letters 1–3 and 4–6 right, but gives the different substring 7–9 the same 6.

A sum doesn't care where each letter stands, so any two strings with the same letters in a different order get the same number.

Numbers written in digits depend on where each digit stands: 123 and 213 have the same digits and are different numbers. Write each letter as its digit: abc is 123 and bac is 213. This number is the hash of the string, and the method is string hashing, also called polynomial hashing.

Hashes pay off most for the substrings of one long string, such as the three parts of abcabcbac. With prefix sums, the sum of any substring is one subtraction, and hashes can work the same way.

The first letters of a string form a prefix: the first 3 letters are the prefix of length 3. With sums, any substring came from the sums of two prefixes, and we want the same here. The number of the prefix of length 3 is 123, and the number of the prefix of length 6 is 123123. Subtracting as with sums gives 123123 − 123 = 123000, not 123. The first three letters moved three places to the left when three more letters were written after them. So move them first: 123 × 1000 = 123000, and 123123 − 123000 = 123, the number of letters 4–6.

In general, multiply the number of the prefix before the substring by 1 followed by as many zeros as the substring has letters, then subtract. These numbers 10, 100, 1000 and so on are the powers of 10. For letters 7–9, the number of the prefix of length 9 is 123123213, and 123123213 − 123123 × 1000 = 213. That is not 123, so letters 4–6 and 7–9 are different.

The hash of a prefix is a prefix hash.

Build: the prefix of length 0 is empty, so its hash at position 0 is 0.

Build: letter 1 is a, code 1. Its code and the hash at position 0 (outlined) give the new hash in blue: 0 × 10 + 1 = 1.

Build: letter 2 is b, code 2: 1 × 10 + 2 = 12.

Build: letter 3 is c, code 3: 12 × 10 + 3 = 123.

Build: letter 4 is a, code 1: 123 × 10 + 1 = 1231.

Build: letter 5 is b, code 2: 1231 × 10 + 2 = 12312.

Build: letter 6 is c, code 3: 12312 × 10 + 3 = 123123.

Build: letter 7 is b, code 2: 123123 × 10 + 2 = 1231232.

Build: letter 8 is a, code 1: 1231232 × 10 + 1 = 12312321.

Build: letter 9 is c, code 3: 12312321 × 10 + 3 = 123123213.

Build: all 10 prefix hashes are written, from 0 to 123123213.

Substring hash: letters 2–3 use the prefix hashes at positions 3 and 1: 123 − 1 × 100 = 23.

Substring hash: letters 5–6 use positions 6 and 4: 123123 − 1231 × 100 = 23.

Compare: 23 = 23, so letters 2–3 and 5–6 are the same substring, bc.

1/14

Fig. 2. Step through string hashing with the buttons or the arrow keys. The bottom row holds the prefix hash at each position; brackets show the substrings being compared.

The run built 10 prefix hashes once. With them and the powers of 10, each of the 45 substrings of the string gets its hash the same way.

Real strings have 26 letters or more. Every code must be a single digit, smaller than the base: with code 12 for l in base 10, the letter l would get the same number as ab. So the base must be larger than 10, and a string of 10^5 letters gives hashes of 10^5 digits.

So we keep only the remainder after division by a large prime, the modulus, as in modular arithmetic. The subtraction still works on remainders. Take remainders by 19: the prefix hash of length 3 is 123, remainder 9; the prefix hash of length 6 is 123123, remainder 3; and 1000 leaves 12. For letters 4–6 this gives 3 − 9 × 12 = −105. That is negative, so add 19 until it isn't: −105 + 6 × 19 = 9. This is the remainder of 123, the hash of letters 4–6.

Fig. 3. On remainders, the same subtraction gives the remainder of the hash, once a negative result is brought back into 0..18.

Equal substrings still get equal remainders. Different substrings can now get the same remainder, though with a prime near 10^9 this is rare.

Finding a pattern

To find a pattern of $m$ letters in a text of $n$ letters, compute the hash of the pattern once, with the same base and modulus, and compare it with the hash of every window of $m$ letters in the text. Each window costs one multiplication and one subtraction, so the search takes O(n + m) time. In abcabcbac, the pattern abc (hash 123) occurs at positions 1 and 4. This method is known as the Rabin–Karp algorithm.

Fig. 4. At each position, the hash of the window is compared with the hash of the pattern, 123.

Substrings of one length

Does some substring of length 3 occur twice in abcabcbac? Go through its windows of 3 letters and put the hash of each into a set. The first three hashes are 123, 231 and 312. The fourth, 123, is already in the set, so abc occurs twice. The same check finds a common substring of length L of two strings: put the hashes of the first string's windows into the set and look up those of the second.

A common substring of length L gives common substrings of every shorter length: drop its last letter. So the answer is "yes" up to some length and "no" after it, and binary search on L finds the longest common substring. Each check puts up to $n$ hashes into a set, which takes O(n \log n), and the search makes about $\log n$ checks, O(n \log^2 n) in total. With up to $n$ hashes in one set, one modulus gives false matches (see the correctness proof), so use two.

Palindromes

A palindrome reads the same in both directions, like bcb. Build the prefix hashes of the reversed string too. Letters l..r of the string, read backwards, are letters n - r + 1 .. n - l + 1 of the reversed string. So letters l..r form a palindrome when their hash equals the hash of those letters of the reversed string. Each check takes $O(1)$ after $O(n)$ preparation.

Fig. 5. Letters 5–7, read backwards, are letters 3–5 of the reversed string. Both are bcb, so their hashes match.

Implementation

Let's keep the prefix hashes in an array h: h[i] is the hash of the prefix of length i, and h[0] = 0, as in prefix sums. Positions count from 1, so letter i is s[i - 1] in the program.

The examples above used base 10 and codes a = 1, b = 2, c = 3 to keep the numbers readable. Different letters need different codes, so the program uses the character itself, s[i] (a is 97).

The base B must be larger than every code (remember l = 12 against ab) and smaller than the modulus. The program draws it at random once at the start. A fixed base can be beaten by a test built against it; a base drawn at run time can't be known when the tests are written. The array p holds the powers of the base: p[i] is B to the power i, so with base 10, p[3] is the 1000 used above.

Every value is a remainder by the modulus M. The program keeps two moduli, 10^9 + 7 and $998244353$, with arrays h1, p1 and h2, p2 for them.

1. Compute the powers: p[0] = 1 and p[i] = p[i - 1] * B % M.

2. Build the prefix hashes: h[0] = 0 and h[i + 1] = (h[i] * B + s[i]) % M.

3. Get the hash of letters l..r: (h[r] - h[l - 1] * p[r - l + 1]) % M, plus M and % M again, because the subtraction can leave a negative number, like the −105 above.

4. Compare: two substrings are equal when they have the same length and equal hashes for both moduli.

The program reads the string, then the number of questions q, then q lines l1 r1 l2 r2 with positions from 1. For each question it prints + if letters l1..r1 equal letters l2..r2 and - otherwise. For the main example the input is:

abcabcbac
3
1 3 4 6
4 6 7 9
2 3 5 6

#include <iostream>
#include <string>
#include <vector>
#include <random>
#include <chrono>
using namespace std;

const long long M1 = 1000000007, M2 = 998244353;

int main() {
    string s;
    cin >> s;
    int n = s.size();

    // a random base: larger than any char code, smaller than both moduli
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    long long B = uniform_int_distribution<long long>(256, 900000000)(rng);

    // compute the powers: p[i] is B to the power i
    vector<long long> p1(n + 1), p2(n + 1);
    p1[0] = p2[0] = 1;
    for (int i = 1; i <= n; i++) {
        p1[i] = p1[i - 1] * B % M1;
        p2[i] = p2[i - 1] * B % M2;
    }

    // build the prefix hashes: h[i] is the hash of the first i letters
    vector<long long> h1(n + 1, 0), h2(n + 1, 0);
    for (int i = 0; i < n; i++) {
        h1[i + 1] = (h1[i] * B + s[i]) % M1;
        h2[i + 1] = (h2[i] * B + s[i]) % M2;
    }

    // get the hash of letters l..r, counted from 1
    auto get1 = [&](int l, int r) { return ((h1[r] - h1[l - 1] * p1[r - l + 1]) % M1 + M1) % M1; };
    auto get2 = [&](int l, int r) { return ((h2[r] - h2[l - 1] * p2[r - l + 1]) % M2 + M2) % M2; };

    int q;
    cin >> q;
    while (q--) {
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;
        // compare: the same length, and equal hashes for both moduli
        bool same = r1 - l1 == r2 - l2
                 && get1(l1, r1) == get1(l2, r2)
                 && get2(l1, r1) == get2(l2, r2);
        cout << (same ? "+" : "-") << "\n";
    }
}

The program takes O(n + q) time and $O(n)$ memory.

Correctness proof

The formula rests on one invariant: after letter $i$ is added, h_i is the remainder of the number whose digits in base $B$ are the codes of the first $i$ letters. It holds for h_0 = 0, and h_{i} = h_{i-1} \cdot B + c_i keeps it, because writing a digit on the right moves all earlier digits one place left. Going from h_{l-1} to h_r writes r - l + 1 more digits, so the first l - 1 letters are moved left r - l + 1 times:

This is the subtraction in the program. Taking remainders after every step doesn't break it, because the remainder of a sum or a product depends only on the remainders of its parts.

Equal substrings have the same codes in the same places, so they always get equal hashes. The other direction can fail. Two different substrings with the same hash are a collision. The figure below shows one: with base 10 and remainders by 19, letters 5–7 (bcb, 232) and letters 7–9 (bac, 213) both leave 4.

Fig. 6. With remainders by 19, two different substrings get the same hash.

For two different substrings of length $L$, the difference of their hashes is a polynomial in $B$ of degree below $L$, whose coefficients are the differences of the codes. For abc against bac it is (1 - 2) \cdot B^2 + (2 - 1) \cdot B + (3 - 3). Not all coefficients are 0, and a nonzero polynomial of degree $d$ has at most $d$ roots modulo a prime, just as over the real numbers. So a random base gives a collision with chance at most $L/M$. This bound is a worst case: for L = 10^5 and $M$ near 10^9 it is 10^{-4} per comparison, which guarantees little over 10^5 questions. In practice, on tests not built against the random base, hashes behave like random numbers below $M$, and two different substrings collide with chance about $1/M$. With one prime near 10^9 and 10^5 questions, a collision in the whole test then has chance about 10^{-4}.

With $k$ hashes in a set and one modulus $M$, about k^2 / (2M) collisions are expected. A test with all 10^5 substrings of length 20 of a random string and the modulus 10^9 + 7 found 5, 3 and 4 collisions for three random bases. Two moduli fix it: the pair of remainders takes about 10^{18} values, and the same set has a collision with chance about 5 \cdot 10^{-9}.

Remainders by 2^{64}

A common shortcut keeps the hashes in unsigned long long and lets overflow take the remainder, by 2^{64}. This modulus is not a prime, and the polynomial argument above fails. Take the Thue–Morse string of length 1024 over a and b: counting from 0, letter $i$ is b when $i$ has an odd number of 1 bits in binary and a otherwise. Swap a and b in it to get a second string. The two strings differ in every letter, yet their hashes by 2^{64} are equal for every odd base. With an even base it is worse: B^{64} is divisible by 2^{64}, so the hash depends only on the last 64 letters. Problem setters add such tests against hashing by 2^{64}, so use prime moduli.

Common mistakes

• Forgetting the + M after the subtraction. With base 131 and 10^9 + 7, letters 1–3 of abcabcbac give 1677554 and letters 4–6 give −998322453, so equal substrings compare unequal.

• Checking a palindrome against the same positions of the reversed string. Letters 5–7 of abcabcbac are the palindrome bcb, but letters 5–7 of cabcbacba are bac, so the check says "no". Compare with letters n - r + 1 .. n - l + 1.

Similar algorithms

The Z-function and the prefix function find every occurrence of a pattern and the periods of a string exactly, in $O(n)$, with no chance of error. They compare positions with the start of one string, while hashing compares any two substrings. When the task is only to find a pattern and a wrong answer is not acceptable, prefer them.

A suffix array sorts all suffixes of a string in O(n \log n). It counts distinct substrings and finds the longest repeated substring exactly. Hashing with binary search on the length is easier to write and slower by a factor of $\log n$.

Manacher's algorithm finds all palindromes of a string exactly in $O(n)$. Use hashing when palindrome checks are one part of a larger hashing solution.

The hash function inside an unordered_set spreads keys over buckets for fast lookup; it is a different thing from string hashing, though such a set can store string hashes.

Practice