Rolling Hash for Fast String Comparison

1. The Problem with Naive String Comparison

Imagine you need to find all occurrences of a pattern string P of length M inside a larger text T of length N. The most straightforward way is to:

1. Take the first substring of T with length M.
2. Compare it character-by-character with P.
3. If it doesn't match, slide the window in T by one character and repeat.

This brute-force approach has a time complexity of O((N-M+1) * M), which simplifies to O(N*M). For large texts and patterns, this is highly inefficient.

The bottleneck is the O(M) comparison at every single position. What if we could perform this comparison in O(1)? This is where hashing comes in.

2. Hashing Strings for O(1) Comparison

The core idea is simple:

• Convert the pattern P into a single number, its hash value.
• Convert each substring of T of length M into a hash value.
• Compare the hash values. Since comparing two numbers is an O(1) operation, we can quickly check for potential matches.

To see this idea in action, let's watch the beginning of a video that introduces the concept.

As the video hints, there are two crucial considerations:

1. How do we design a good hash function? A naive function might lead to too many "false positives."
2. How do we compute the hash of each new substring efficiently? Recalculating it from scratch each time would still be O(M).

Let's tackle the first question.

3. Polynomial Rolling Hash: A Good Hash Function

A simple hash function, like summing the ASCII values of characters, is flawed. For example, "abc" and "cba" would have the same hash. We need a function where the order of characters matters. The standard solution is the Polynomial Rolling Hash.

The formula for this hash function is:
$hash(s)=(s[0]\cdot p^0+s[1]\cdot p^1+s[2]\cdot p^2+\cdots +s[n-1]\cdot p^{n-1})(\mathrm{mod}m)$

Let's break down the components:

• s[i]: The numeric value of the character at index i. For lowercase English letters, we typically map 'a' to 1, 'b' to 2, and so on. So, s[i] = s.charAt(i) - 'a' + 1.
• p: A prime number, chosen to be greater than the number of characters in the alphabet (e.g., for lowercase English, p >= 27). Common choices are 31 or 37.
• m: A very large prime number (e.g., 10^9 + 7). This is the modulus, used to keep the hash value within the limits of standard integer types (like long in Java) and prevent overflow.

Let's study this formula and its Java implementation more closely.

A crucial point to remember is that even with a good hash function, collisions can occur (two different strings mapping to the same hash). The probability is low if m is large, but it's not zero. Therefore, if the hashes match, you must perform a final character-by-character comparison to confirm a true match. If the hashes do not match, you are guaranteed that the strings are different.

4. The "Rolling" Update: O(1) Hash Calculation

Now for the second, and most clever, part. How do we avoid recalculating the hash for every substring? We "roll" it.

Let's use a slightly different (and easier to roll) version of the polynomial hash formula:
$hash(s)=(s[0]\cdot p^{n-1}+s[1]\cdot p^{n-2}+\cdots +s[n-1]\cdot p^0)(\mathrm{mod}m)$

Suppose we have the hash for the substring T[i..i+M-1]. To get the hash for the next substring T[i+1..i+M], we need to:

1. Remove the contribution of the leftmost character, T[i].
2. Shift the remaining hash value to the left (multiply by p).
3. Add the contribution of the new rightmost character, T[i+M].

The update rule looks like this:
hash_old = (T[i] * p^(M-1) + T[i+1] * p^(M-2) + ...)
hash_new = ( (hash_old - T[i] * p^(M-1)) * p + T[i+M] ) % m

This update is an O(1) operation! To see a visual explanation and a practical implementation of this, let's watch two more resources.

5. Implementation in Java

Here is a robust Java implementation for a RollingHash class that uses the principles we've discussed. It uses the (hash_old - T[i] * p^(M-1)) * p + T[i+M] update rule.

public class RollingHash {
    private static final long p = 31; // Prime base
    private static final long m = 1_000_000_007; // Large prime modulus

    private long hashValue;
    private int windowSize;
    private String text;
    private int currentIndex;

    private long p_pow_M_minus_1; // To store p^(M-1) % m

    // Constructor for the initial window
    public RollingHash(String text, int windowSize) {
        this.text = text;
        this.windowSize = windowSize;
        this.currentIndex = 0;
        this.hashValue = 0;
        
        // Pre-calculate p^(M-1) % m
        this.p_pow_M_minus_1 = 1;
        for (int i = 0; i < windowSize - 1; i++) {
            this.p_pow_M_minus_1 = (this.p_pow_M_minus_1 * p) % m;
        }

        // Calculate hash for the first window
        for (int i = 0; i < windowSize; i++) {
            this.hashValue = (this.hashValue * p + (text.charAt(i) - 'a' + 1)) % m;
        }
    }

    public long getHash() {
        return hashValue;
    }

    // Rolls the hash to the next window
    public void roll() {
        if (currentIndex + windowSize < text.length()) {
            char oldChar = text.charAt(currentIndex);
            char newChar = text.charAt(currentIndex + windowSize);

            // 1. Remove old character's contribution
            long oldCharContribution = ((oldChar - 'a' + 1) * p_pow_M_minus_1) % m;
            hashValue = (hashValue - oldCharContribution + m) % m; // add m to handle negative result

            // 2. Shift hash to the left
            hashValue = (hashValue * p) % m;

            // 3. Add new character's contribution
            hashValue = (hashValue + (newChar - 'a' + 1)) % m;

            currentIndex++;
        }
    }
}

This class can be used to efficiently get the hash of every M-length substring in a text. You create an instance for the first window and then call roll() in a loop.

6. Minimizing Collisions with Dual Hashing

For competitive programming and very reliable checks, a single hash function might not be enough. To reduce the collision probability to a near-zero level, you can use two different hash functions.

The idea is simple:

1. Choose two different pairs of (p, m). For example, (p1=31, m1=10^9+7) and (p2=37, m2=10^9+9).
2. Calculate two hash values for every string.
3. Two strings are considered equal only if both of their hash value pairs are equal.

The probability of collision drops from 1/m to 1/(m1*m2), which is practically negligible.

Conclusion

You've now learned the mechanics of polynomial rolling hash, a cornerstone technique for efficient string algorithms. It allows you to transform substrings into numerical fingerprints that can be compared and updated in constant time.

Key Takeaways:

• String Hashing converts strings to numbers for O(1) comparison, but requires a character-by-character check on hash match to handle collisions.
• Polynomial Rolling Hash is the standard, weighting characters by powers of a prime base p to preserve order information.
• All calculations are done modulo a large prime m to prevent integer overflow.
• The "rolling" update allows the hash of a sliding window to be recalculated in O(1) time by subtracting the old character and adding the new one.
• Dual Hashing (using two different p and m pairs) dramatically reduces collision probability and is a standard practice in competitive programming.

Preview of the next lesson:
Now that we have a solid grasp of how to create and roll a hash, we are ready to build a full pattern-matching algorithm. In the next lesson, we will implement the Rabin-Karp algorithm, which uses this exact rolling hash technique to find a pattern in a text with an average time complexity of O(N+M).