String Hashing and Rabin-Karp Algorithm: A Competitive Programming Guide

Introduction

String matching is a common problem in competitive programming and software development. Given a large text and a pattern, we often need to determine whether the pattern appears in the text or compare multiple substrings efficiently.

A naive approach compares characters one by one, which can become slow for large inputs. To overcome this limitation, we use String Hashing, the foundation of the Rabin-Karp Algorithm.

String hashing allows us to compare substrings in constant time after preprocessing, making it an extremely powerful tool for solving advanced string problems.

What is String Hashing?

String hashing converts a string into a numerical value called a hash.

Instead of comparing entire strings character by character, we compare their hash values.

Example

"code"  ->  123456789
"forces" -> 987654321

If two substrings have different hashes, they are definitely different.

If two substrings have the same hash, they are very likely to be equal.

Polynomial Rolling Hash

The most common hashing technique in competitive programming is the polynomial rolling hash.

For a string:

s = s0 s1 s2 ... sn

The hash is computed as:

Hash(s) =
(s0 × p^0 +
 s1 × p^1 +
 s2 × p^2 + ...)
 mod M

Where:

• p = base (commonly 31 or 37)

• M = large prime modulus

• characters are mapped to integers

Example:

a -> 1
b -> 2
c -> 3
...
z -> 26

Why Prefix Hashes?

Suppose we need hashes of many substrings.

Computing each hash independently would require:

O(length of substring)

Instead, we precompute prefix hashes and powers of the base.

This allows us to obtain any substring hash in:

O(1)

time.

Prefix Hash Formula

Let:

pref[i]

represent the hash of the prefix ending at index i.

Then:

hash(l, r)
=
(pref[r] - pref[l-1])
× inverse(p^l)

This normalization step ensures equal substrings produce equal hashes regardless of position.

Double Hashing

A major issue with hashing is collisions.

Two different strings can occasionally produce the same hash.

To reduce this probability, we use two moduli:

1e9+9
1e8+7

and store:

(hash1, hash2)

instead of a single hash.

The probability of collision becomes extremely small.

Your implementation uses exactly this technique.

Rabin-Karp Algorithm

The Rabin-Karp algorithm uses rolling hashes for pattern matching.

Problem

Given:

Text    = "ababcabc"
Pattern = "abc"

Find all occurrences of the pattern.

Idea

1. Compute hash of the pattern.

2. Compute hash of every substring of equal length.

3. Compare hashes.

4. If hashes match, report occurrence.

Instead of comparing characters repeatedly, we compare integers.

Time Complexity

Naive Approach

O(N × M)

Where:

• N = text length

• M = pattern length

Rabin-Karp with Hashing

Preprocessing: O(N)
Query: O(1)
Total: O(N)

This makes it suitable for large inputs commonly seen in programming contests.

Applications in Competitive Programming

String hashing appears in many advanced problems.

Common Uses

• Pattern matching

• Rabin-Karp algorithm

• Palindrome checking

• Longest common substring

• Distinct substring counting

• String equality queries

• Binary search on answers involving strings

Many Codeforces and ICPC problems rely on hashing as a core technique.

Understanding the Implementation

The provided implementation supports:

Features

• Polynomial rolling hash

• Double hashing

• Prefix hash preprocessing

• Modular inverse normalization

• O(1) substring hash queries

Example Usage

string s;
cin >> s;

Hashing hs(s);

int l = 2;
int r = 5;

vector<ll> hashValue = hs.substringHash(l, r);

The function returns the normalized hash of substring:

s[l...r]

Using two independent moduli.

Comparing Two Substrings

One of the most common applications is substring comparison.

if(hs.substringHash(l1, r1) ==
   hs.substringHash(l2, r2))
{
    cout << "Equal";
}

This comparison runs in:

O(1)

time.

Common Mistakes

1. Using a Single Modulus

This increases collision probability.

Prefer double hashing whenever possible.

2. Forgetting Normalization

Hashes computed at different positions must be normalized before comparison.

3. Small Modulus

Always use large prime moduli.

Examples:

1000000007
1000000009

4. Integer Overflow

Use long long when performing modular multiplication.

Key Takeaways

• String hashing converts strings into numerical fingerprints.

• Prefix hashes allow O(1) substring hash queries.

• Rabin-Karp uses hashing for efficient pattern matching.

• Double hashing significantly reduces collisions.

• String hashing is a fundamental technique in competitive programming.

• Applications include substring comparison, palindrome problems, and advanced string algorithms.

Conclusion

String hashing is one of the most powerful tools in a competitive programmer's toolkit. By preprocessing prefix hashes and powers of a base, we can compare substrings in constant time and solve complex string problems efficiently. The Rabin-Karp algorithm is a classic example of how hashing transforms an expensive string matching problem into a fast and practical solution.

The double-hashing implementation presented here is suitable for most competitive programming tasks and serves as a strong foundation for advanced string algorithms.

CPP Template :-

#include <bits/stdc++.h>
using namespace std;

void fastIO() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

typedef long long ll;
constexpr char nl = '\n';

ll modMul(ll a, ll b, ll mod) {
    return (a * b) % mod;
}

ll modSub(ll a, ll b, ll mod) {
    return ((a - b) % mod + mod) % mod;
}

ll binExp(ll a, ll b, ll mod) {
    ll res = 1;
    while (b > 0) {
        if (b & 1) res = modMul(res, a, mod);
        a = modMul(a, a, mod);
        b >>= 1;
    }
    return res;
}

ll modInvPrime(ll a, ll mod) {
    return binExp(a, mod - 2, mod);
}

struct Hashing {
    string s;
    int n;
    int primes;

    const ll base = 31;
    vector<ll> hashPrimes = {1000000009LL, 100000007LL};
    vector<vector<ll>> hashValues;
    vector<vector<ll>> powersOfBase;
    vector<vector<ll>> inversePowersOfBase;

    Hashing(const string& str) {
        s = str;
        n = (int)s.size();
        primes = (int)hashPrimes.size();

        hashValues.resize(primes);
        powersOfBase.resize(primes);
        inversePowersOfBase.resize(primes);

        for (int i = 0; i < primes; i++) {
            ll mod = hashPrimes[i];
            powersOfBase[i].resize(n + 1);
            inversePowersOfBase[i].resize(n + 1);
            powersOfBase[i][0] = 1;
            for (int j = 1; j <= n; j++) {
                powersOfBase[i][j] = modMul(powersOfBase[i][j - 1], base, mod);
            }

            inversePowersOfBase[i][n] = modInvPrime(powersOfBase[i][n], mod);
            for (int j = n - 1; j >= 0; j--) {
                inversePowersOfBase[i][j] =
                    modMul(inversePowersOfBase[i][j + 1], base, mod);
            }
        }

        for (int i = 0; i < primes; i++) {
            ll mod = hashPrimes[i];
            hashValues[i].resize(n);
            for (int j = 0; j < n; j++) {
                hashValues[i][j] =
                    modMul((s[j] - 'a' + 1LL), powersOfBase[i][j], mod);

                if (j > 0) {
                    hashValues[i][j] =
                        (hashValues[i][j] + hashValues[i][j - 1]) % mod;
                }
            }
        }
    }

    vector<ll> substringHash(int l, int r) {
        vector<ll> hash(primes);

        for (int i = 0; i < primes; i++) {
            ll mod = hashPrimes[i];

            ll rightHash = hashValues[i][r];
            ll leftHash = (l > 0 ? hashValues[i][l - 1] : 0LL);

            hash[i] = modMul(
                modSub(rightHash, leftHash, mod),
                inversePowersOfBase[i][l],
                mod
            );
        }

        return hash;
    }
};

int main() {
    fastIO();
    string s; cin >> s;
    Hashing hs(s);
    // Example:
    // hash of substring s[l...r]
    int l = 0, r = (int)s.size() - 1;
    vector<ll> h = hs.substringHash(l, r);
    cout << h[0] << ' ' << h[1] << nl;

    return 0;
}