Hashing and Rabin–Karp

What is a hash function?

A hash function takes an input and produces a number. With the function written below (p = 29):

hash("hello")  → 81236064
hash("world")  → 73461324
hash("abc")    → 86198

Properties of good hash functions

1. Deterministic: the same input always produces the same output
2. Fast to compute: O(n) for a string of length n
3. Uniform distribution: hash values spread evenly
4. Minimizes collisions: different inputs should produce different hashes (ideally)

Why do we need hashing?

m is the length of a string.

Polynomial rolling hash

• p is a prime, commonly 29 or 31 for lowercase letters
• s[i] is the ASCII code of the character at position i

Example: hash("abc") with p = 29

hash = 'a' × 29^0 + 'b' × 29^1 + 'c' × 29^2
     = 97 × 1 + 98 × 29 + 99 × 841
     = 97 + 2842 + 83259
     = 86198

Simple hash implementation

#include <iostream>
using namespace std;

int get_hash(string s) {
    int p = 29;
    int p_pow = 1;  // p^0
    int h = 0;

    for (int i = 0; i < s.size(); i++) {
        h += s[i] * p_pow;
        p_pow *= p;
    }

    return h;
}

int main() {
    cout << "hash('abc') = " << get_hash("abc") << endl;
    cout << "hash('hello') = " << get_hash("hello") << endl;
    cout << "hash('world') = " << get_hash("world") << endl;

    return 0;
}

hash('abc') = 86198
hash('hello') = 81236064
hash('world') = 73461324

Another version · p = 31, compare two strings

The same function with p = 31: read two strings, print both hashes and whether they are equal.

#include <iostream>

using namespace std;

int get_hash(string s) {
    int h = 0;
    int p = 31;
    int p_pow = 1;
    for (int i = 0; i < s.size(); i++) {
        h += s[i] * p_pow;
        p_pow *= p;
    }
    return h;
}

int main() {
    string s1, s2;
    cin >> s1 >> s2;
    cout << get_hash(s1) << " " << get_hash(s2) << " " << (get_hash(s1) == get_hash(s2));
    return 0;
}

abc bca

98274 96384 0

Same letters, different order — different hash, because every position has its own power of p.

Naive solution — O(n² × m)

// Compare each pair of strings
for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
        if (strings[i] == strings[j]) {  // O(m) comparison
            cout << i << " " << j << endl;
        }
    }
}

// Time Complexity: O(n² × m)
// where n = number of strings, m = average string length

Improved solution with hashing — O(n × m)

1. Compute the hash of each string — O(m) per string
2. Store the hashes in a map
3. Compare hash values instead of strings — O(1)

#include <iostream>
#include <vector>
#include <map>
using namespace std;

int get_hash(string s) {
    int p = 29;
    int p_pow = 1;
    int h = 0;
    for (int i = 0; i < s.size(); i++) {
        h += s[i] * p_pow;
        p_pow *= p;
    }
    return h;
}

int main() {
    int n;
    cin >> n;

    vector<string> strings(n);
    map<int, vector<int>> hash_map;  // hash -> indices

    // Compute hash for each string and group by hash
    for (int i = 0; i < n; i++) {
        cin >> strings[i];
        int h = get_hash(strings[i]);
        hash_map[h].push_back(i);
    }

    // Find pairs with same hash
    cout << "Identical string pairs:" << endl;
    for (auto& pair : hash_map) {
        vector<int>& indices = pair.second;
        // All strings with same hash are potentially identical
        for (int i = 0; i < indices.size(); i++) {
            for (int j = i + 1; j < indices.size(); j++) {
                // Double-check actual strings to avoid hash collisions
                if (strings[indices[i]] == strings[indices[j]]) {
                    cout << indices[i] << " " << indices[j] << endl;
                }
            }
        }
    }

    return 0;
}

5
hello
world
hello
test
world

Identical string pairs:
1 4
0 2

Pairs come out grouped by hash, in the order of the map keys: hash("world") is smaller than hash("hello"), so 1 4 is printed first.

Time complexity: O(n × m)

• Computing hashes: O(n × m)
• Grouping by hash: O(n)
• Finding pairs: O(n) if there are no collisions

Instead of O(n² × m) we get O(n × m).

The problem

• A string of length n has O(n²) substrings
• Computing each hash takes O(m)
• Total: O(n³) — too slow

Prefix hash array

h[i] = hash of the prefix s[0…i]:

vector<int> get_h(string s) {
    int n = s.size();
    vector<int> h(n);

    h[0] = s[0];          // First character
    int p = 29;
    int p_pow = 29;       // p^1

    for (int i = 1; i < n; i++) {
        h[i] = h[i - 1] + s[i] * p_pow;
        p_pow *= p;
    }

    return h;
}

Example: s = "abcd", p = 29

h[0] = 'a' × p^0 = 97
h[1] = 'a' × p^0 + 'b' × p^1 = 2939
h[2] = 'a' × p^0 + 'b' × p^1 + 'c' × p^2 = 86198
h[3] = 'a' × p^0 + 'b' × p^1 + 'c' × p^2 + 'd' × p^3 = 2525098

Getting the hash of any substring

hash(s[l...r]) = (h[r] - h[l-1]) / p^l

But we cannot divide, so we multiply the other side:

hash(s[l...r]) × p^l = h[r] - h[l-1]

// Precompute powers of p
vector<int> p(n);
p[0] = 1;
for (int i = 1; i < n; i++)
    p[i] = p[i - 1] * 29;

// Get hash of substring [l, r]
int substring_hash(int l, int r) {
    int hash = h[r];
    if (l > 0)
        hash = hash - h[l - 1];
    return hash;  // This equals original_hash × p^l
}

So to compare two substrings, bring both to the same power of p before comparing.

Naive approach — O(n × m)

for (int i = 0; i <= n - m; i++) {
    bool match = true;
    for (int j = 0; j < m; j++) {
        if (s1[i + j] != s2[j]) {
            match = false;
            break;
        }
    }
    if (match)
        cout << "Found at position " << i << endl;
}

Rabin–Karp — O(n + m)

1. Compute the hash of the pattern s2
2. Compute the prefix hashes of the text s1
3. At each position i, compare the hash of the window with the pattern hash
4. Compare the actual strings only if the hashes match — to handle collisions

Complete implementation

// unsigned long long: with int the hash overflows already at 7 characters
#include <iostream>
#include <vector>

using namespace std;

// Compute hash of entire string
unsigned long long get_hash(string s) {
    unsigned long long p = 29;
    unsigned long long p_pow = 1;  // p^0
    unsigned long long h = 0;

    for (int i = 0; i < s.size(); i++) {
        h += s[i] * p_pow;
        p_pow *= p;
    }

    return h;
}

// Compute prefix hash array
vector<unsigned long long> get_h(string s) {
    int n = s.size();
    vector<unsigned long long> h(n);

    h[0] = s[0];
    unsigned long long p = 29;
    unsigned long long p_pow = 29;  // p^1

    for (int i = 1; i < n; i++) {
        h[i] = h[i - 1] + s[i] * p_pow;
        p_pow *= p;
    }

    return h;
}

int main() {
    string s1, s2;
    cin >> s1 >> s2;

    // Precompute powers of p
    vector<unsigned long long> p(s1.size());
    p[0] = 1;
    for (int i = 1; i < s1.size(); i++)
        p[i] = p[i - 1] * 29;

    // Hash of pattern
    unsigned long long h_s2 = get_hash(s2);

    // Prefix hashes of text
    vector<unsigned long long> h = get_h(s1);

    int n = s1.size();
    int m = s2.size();

    // Find all occurrences
    for (int i = 0; i < n - m + 1; i++) {
        int j = i + m - 1;  // End of current window

        // Get hash of substring s1[i...j]
        unsigned long long hash = h[j];
        if (i > 0)
            hash = hash - h[i - 1];

        // Compare with pattern hash
        // hash = actual_hash × p^i, so compare with h_s2 × p^i
        if (hash == h_s2 * p[i])
            cout << i << " ";
    }

    return 0;
}

ababcab ab

0 2 5

Trace: s1 = "ababcab", s2 = "ab"

Step 1: hash of the pattern "ab"
  h_s2 = 'a' × 29^0 + 'b' × 29^1 = 97 + 2842 = 2939

Step 2: prefix hashes of "ababcab"
  h[0] = 97           (hash of "a")
  h[1] = 2939         (hash of "ab")
  h[2] = 84516        (hash of "aba")
  h[3] = 2474638      (hash of "abab")
  h[4] = 72495457     (hash of "ababc")
  h[5] = 2062076910   (hash of "ababca")
  h[6] = 60354762368  (hash of "ababcab")

Step 3: check each position
Position 0: substring "ab"
  hash = h[1] = 2939
  h_s2 × p[0] = 2939 × 1 = 2939
  Match! Output: 0

Position 1: substring "ba"
  hash = h[2] - h[0] = 84516 - 97 = 84419
  h_s2 × p[1] = 2939 × 29 = 85231
  No match

Position 2: substring "ab"
  hash = h[3] - h[1] = 2474638 - 2939 = 2471699
  h_s2 × p[2] = 2939 × 841 = 2471699
  Match! Output: 2

Position 3: substring "bc"
  hash = h[4] - h[2] = 72495457 - 84516 = 72410941
  h_s2 × p[3] = 2939 × 24389 = 71679271
  No match

Position 4: substring "ca"
  hash = h[5] - h[3] = 2062076910 - 2474638 = 2059602272
  h_s2 × p[4] = 2939 × 707281 = 2078698859
  No match

Position 5: substring "ab"
  hash = h[6] - h[4] = 60354762368 - 72495457 = 60282266911
  h_s2 × p[5] = 2939 × 20511149 = 60282266911
  Match! Output: 5

Output: 0 2 5 — the positions where "ab" occurs.

Time complexity

Much better than the naive O(n × m).

Another version · p = 31

The same search with p = 31 and the pattern called t.

// unsigned long long: with int the hash overflows already at 7 characters
#include <iostream>
#include <vector>

using namespace std;

unsigned long long get_hash(string s) {
    unsigned long long h = 0;
    unsigned long long p = 31;
    unsigned long long p_pow = 1;
    for (int i = 0; i < s.size(); i++) {
        h += s[i] * p_pow;
        p_pow *= p;
    }
    return h;
} 

vector<unsigned long long> get_h(string s) {
    int n = s.size();
    vector<unsigned long long> h(n);
    h[0] = s[0];
    unsigned long long p = 31;
    unsigned long long p_pow = 31;
    for (int i = 1; i < n; i++) {
        h[i] = h[i - 1] + s[i] * p_pow;
        p_pow *= p;
    }
    return h;
}

int main() {
    string s, t;
    cin >> s >> t;
    int n = s.size();
    int m = t.size();
    unsigned long long h_t = get_hash(t);
    vector<unsigned long long> h = get_h(s);
    vector<unsigned long long> p(n);
    p[0] = 1;
    for (int i = 1; i < n; i++)
        p[i] = p[i - 1] * 31;
    // cout << h_t << endl;
    // for (int i = 0; i < n; i++)
    //     cout << h[i] << " ";
    for (int i = 0; i < n - m + 1; i++) {
        int j = i + m - 1;
        unsigned long long h_i_j = h[j];
        if (i > 0) 
            h_i_j -= h[i - 1];
        if (h_i_j == h_t * p[i])
            cout << i << " ";
    }
    return 0;
}

abacaba aba

0 4

Naive solution — O(n³)

set<string> distinct;
for (int i = 0; i < n; i++) {
    for (int j = i; j < n; j++) {
        string sub = s.substr(i, j - i + 1);  // O(n)
        distinct.insert(sub);  // O(n log n) for set insertion
    }
}
cout << distinct.size() << endl;

// Time: O(n² × n) = O(n³)

Improved solution with hashing — O(n² log n)

#include <iostream>
#include <vector>
#include <set>
using namespace std;

vector<unsigned long long> get_h(string s) {
    int n = s.size();
    vector<unsigned long long> h(n);

    h[0] = s[0];
    unsigned long long p = 29;
    unsigned long long p_pow = 29;

    for (int i = 1; i < n; i++) {
        h[i] = h[i - 1] + s[i] * p_pow;
        p_pow *= p;
    }

    return h;
}

int main() {
    string s;
    cin >> s;

    int n = s.size();

    // Precompute powers
    vector<unsigned long long> p(n);
    p[0] = 1;
    for (int i = 1; i < n; i++)
        p[i] = p[i - 1] * 29;

    // Compute prefix hashes
    vector<unsigned long long> h = get_h(s);

    // Use set to store unique hashes
    set<unsigned long long> distinct_hashes;

    // Generate all substrings
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            // Hash of substring [i, j]
            unsigned long long hash = h[j];
            if (i > 0)
                hash = hash - h[i - 1];

            // added: h[j] - h[i-1] is hash × p^i — bring every substring to p^(n-1),
            // otherwise the same substring at two positions gives two numbers
            distinct_hashes.insert(hash * p[n - 1 - i]);  // O(log n)
        }
    }

    cout << "Number of distinct substrings: ";
    cout << distinct_hashes.size() << endl;

    return 0;
}

abab

Number of distinct substrings: 7

h[j] − h[i−1] is the hash × p^i. Multiplying by p^(n−1−i) gives every substring the same factor p^(n−1), so equal substrings give equal numbers.

Time complexity

From O(n³) down to O(n² log n).

Example: s = "abab"

Length 1: a, b, a, b           → 2 distinct (a, b)
Length 2: ab, ba, ab           → 2 distinct (ab, ba)
Length 3: aba, bab             → 2 distinct (aba, bab)
Length 4: abab                 → 1 distinct (abab)

Total distinct: 7

With hashing:

Substrings and their hashes:
"a"    → hash1
"b"    → hash2
"a"    → hash1  (duplicate)
"b"    → hash2  (duplicate)
"ab"   → hash3
"ba"   → hash4
"ab"   → hash3  (duplicate)
"aba"  → hash5
"bab"  → hash6
"abab" → hash7

Set contains: {hash1, hash2, hash3, hash4, hash5, hash6, hash7}
Count = 7

What is a collision?

hash("abc") == hash("xyz")  // Collision!

Why do collisions happen?

• Hash values are integers — a finite range
• Strings are infinite in variety
• By the pigeonhole principle, collisions are inevitable

1 · Use larger hash values (long long, unsigned long long)

unsigned long long get_hash(string s) {
    unsigned long long p = 29;
    unsigned long long p_pow = 1;
    unsigned long long h = 0;
    for (int i = 0; i < s.size(); i++) {
        h += s[i] * p_pow;
        p_pow *= p;
    }
    return h;
}

2 · Use modulo with a large prime

const long long MOD = 1e9 + 7;  // Large prime

int get_hash(string s) {
    long long h = 0;
    long long p_pow = 1;
    long long p = 29;

    for (int i = 0; i < s.size(); i++) {
        h = (h + s[i] * p_pow) % MOD;
        p_pow = (p_pow * p) % MOD;
    }

    return h;
}

3 · Double hashing — two different hash functions

pair<int, int> double_hash(string s) {
    int h1 = get_hash(s, 29, MOD1);
    int h2 = get_hash(s, 31, MOD2);
    return {h1, h2};
}

4 · Verify with an actual string comparison when hashes match

if (hash1 == hash2) {
    // Don't assume strings are equal!
    if (s1 == s2) {
        // Actually equal
    }
}

Where hashing is used

Q1 · Why use prime numbers (29, 31) for p?

Prime numbers reduce the probability of collisions — they spread the hash values better across the range.

Q2 · What if hash values overflow?

• Use long long or unsigned long long
• Use modulo with a large prime: hash = (hash + value) % MOD
• Both work — choose based on the requirements

With plain int the hash of a 7-character string already overflows; signed overflow is undefined behaviour in C++, unsigned overflow simply wraps around.

Q3 · Can we always trust hash equality?

No. When correctness is critical, verify with an actual comparison:

if (hash1 == hash2 && str1 == str2) {
    // Strings are definitely equal
}

Q4 · Rabin–Karp or KMP for pattern matching?

• Rabin–Karp: simpler, works for multiple patterns, small chance of a collision
• KMP: more involved, but no false positives — better for a single pattern

Q5 · Why O(n² log n) for counting distinct substrings?

• O(n²) to generate all substrings
• O(log n) to insert each hash into a set (a balanced tree)
• Total: O(n² log n)

Eight things to remember

1. Hashing converts strings to integers for fast comparison
2. Polynomial rolling hash is the most common for strings: hash = Σ s[i] × p^i
3. A prefix hash array answers substring hash queries in O(1)
4. Rabin–Karp finds a pattern in O(n + m)
5. Hash collisions are possible — verify when necessary
6. Hashing improves complexity — from O(n³) to O(n² log n) or better
7. Choose good parameters: p = 29 or 31, MOD = a large prime
8. Trade-off: speed against a small collision probability

Try these

1. Find all occurrences of a pattern in a text using Rabin–Karp
2. Find the longest duplicate substring
3. Count palindromic substrings using hashing
4. Find the longest common substring of two strings
5. Group anagrams using hash values
6. Detect if two strings are rotations of each other
7. Find the smallest window containing all characters
8. Implement an efficient spell checker using hashing

Problem to topic