Rolling Hash Algorithm: Complete Implementation Guide

1. Introduction and Core Concepts

The rolling hash algorithm is a fundamental technique in string algorithms that enables efficient substring search, fingerprinting, and comparison by computing hash values in constant time as a window slides across a text. Unlike traditional hashing where each substring is hashed independently from scratch, a rolling hash reuses the previous hash value to compute the next one by removing the contribution of the outgoing character and adding the contribution of the incoming character. This incremental approach is what makes the rolling hash algorithm exceptionally powerful for large-scale text processing.

At its core, the rolling hash algorithm transforms a string of characters into a numeric fingerprint. This fingerprint serves as a compact representation of the string, allowing for rapid equality checks without direct character-by-character comparison. The most common formulation is the polynomial rolling hash, often called the Rabin-Karp hash, which treats a string as a number in a base-b number system. For a string s = s[0]s[1]...s[m-1], the hash is computed as H(s) = s[0]*b^(m-1) + s[1]*b^(m-2) + ... + s[m-1]*b^0 mod M, where b is a chosen base (typically larger than the alphabet size) and M is a large modulus to keep the value within bounds.

Why does the rolling hash algorithm matter so much today? Modern computing deals with massive amounts of textual data — from source code repositories and genomic sequences to network packets and plagiarism detection systems. A naive substring search that compares every position character-by-character requires O(n*m) time in the worst case, which becomes prohibitive when n is in the millions or billions. The rolling hash algorithm reduces the average-case search time to O(n+m), making it feasible to search for patterns in huge documents, detect duplicate content across the web, and implement efficient data synchronization protocols like rsync. Its ability to compute hashes on the fly also makes it ideal for streaming data where the entire input is not available at once.

The Fingerprinting Intuition

Think of the rolling hash algorithm as creating a unique fingerprint for every substring of a fixed length. Just as a human fingerprint identifies a person without needing to examine their entire DNA, a hash value identifies a string without storing the entire string. When two hashes match, the underlying strings are very likely to be identical, and a final verification step can confirm equality. This two-step process — fast hash comparison followed by occasional verification — is the key to its efficiency.

Another core concept is the choice of base and modulus. The base should be larger than the number of distinct characters to avoid collisions caused by different permutations producing the same hash. For lowercase English letters, a base of 26, 31, or 256 is common. The modulus is typically a large prime number such as 10^9+7 or 10^9+9, which distributes hash values uniformly and minimizes collisions. Using a single modulus carries a small risk of collision, which is why production systems often use double hashing with two independent moduli.

2. How It Works

The mechanism of the rolling hash algorithm is elegant and can be understood in three phases: initial hash computation, the rolling update, and collision handling. First, the hash of the initial window (the first m characters of the text) is computed using the polynomial formula. This takes O(m) time. For example, to hash the string "abc" with base 256 and modulus 101, we compute (97*256^2 + 98*256 + 99) mod 101, where 97, 98, 99 are ASCII values.

The true power emerges in the second phase: the rolling update. Suppose we have the hash of window T[i : i+m] and want the hash of the next window T[i+1 : i+m+1]. Instead of recomputing from scratch, we apply the recurrence: H_next = ( (H_current - T[i] * b^(m-1)) * b + T[i+m] ) mod M. In words, we subtract the contribution of the character leaving the window (multiplied by the highest power of the base), multiply the remaining value by the base to shift all characters left by one position, and then add the new character entering the window. All operations are performed modulo M to prevent overflow. This update is O(1), which is the defining characteristic of the rolling hash algorithm.

The third phase addresses hash collisions — the scenario where two different strings produce the same hash value. Because the modulus M is finite, collisions are inevitable by the pigeonhole principle, though a good choice of M makes them rare. When a hash match is found between the pattern and a text window, the algorithm must verify the match by directly comparing the characters to rule out a false positive. This verification is O(m) but happens infrequently if the hash function is well-designed, so it does not dominate the average-case runtime.

Mathematical Foundation of Polynomial Hashing

The polynomial formulation is not arbitrary; it ensures that the order of characters matters. The string "ab" and "ba" will have different hashes because 'a'*b + 'b' is not equal to 'b'*b + 'a' unless a equals b. The precomputation of powers b^i mod M is crucial for efficiency. By precomputing an array pow where pow[i] = b^i mod M for i from 0 to n, both the initial hash and every rolling update can be performed with just a few modular multiplications and additions. This precomputation is O(n) time and space and is done once per search.

Modular arithmetic properties make the rolling operation correct. Specifically, (A - B) mod M = (A mod M - B mod M + M) mod M ensures that subtraction never yields a negative intermediate result, and (A * B) mod M = ((A mod M) * (B mod M)) mod M keeps numbers small. Without careful handling of negative values after subtraction, many implementations produce incorrect hashes. A robust implementation always adds M before taking the final modulus.

Rabin-Karp Framework

The rolling hash algorithm is most famously used within the Rabin-Karp string search algorithm. Rabin-Karp uses the rolling hash to find all occurrences of a pattern P of length m in a text T of length n. It computes the hash of P, then iteratively computes the rolling hash of every m-length window in T. Whenever the hashes match, it verifies the substring. While its worst-case time is O(n*m) if every window collides and requires verification, its expected time with a good hash function is O(n+m), which is competitive with more complex algorithms like Knuth-Morris-Pratt while being far simpler to implement and able to search for multiple patterns simultaneously.

3. Implementation

Implementing the rolling hash algorithm correctly requires attention to modular arithmetic, precomputation, and edge cases such as empty strings or patterns longer than the text. Below are four progressively more complete Python implementations that demonstrate the core ideas and production-ready optimizations.

Basic Polynomial Hash Function

This first example shows how to compute the hash of a single string from scratch. It serves as the building block for the rolling version and illustrates the polynomial formula directly.

# Basic polynomial rolling hash for a single string
def polynomial_hash(s, base=256, mod=10**9+7):
    """
    Compute polynomial hash of string s.
    H(s) = s[0]*base^(m-1) + s[1]*base^(m-2) + ... + s[m-1]*base^0 mod mod
    """
    hash_value = 0
    for char in s:
        # Shift previous hash and add new character
        # ord(char) gives ASCII value, ensures distinct values for distinct chars
        hash_value = (hash_value * base + ord(char)) % mod
    return hash_value

# Example usage
text = "hello"
print(polynomial_hash(text))  # Deterministic fingerprint for "hello"
print(polynomial_hash("hello") == polynomial_hash("hello"))  # True
print(polynomial_hash("hello") == polynomial_hash("world"))  # Almost certainly False

Complete Rabin-Karp with Rolling Update

This implementation demonstrates the full rolling hash algorithm for pattern searching, including O(1) window updates and collision verification. Note the careful handling of the highest power and negative modulus.

def rabin_karp_search(text, pattern, base=256, mod=101):
    """
    Search for pattern in text using rolling hash algorithm.
    Returns list of starting indices where pattern is found.
    """
    n = len(text)
    m = len(pattern)
    if m == 0 or m > n:
        return []

    # Precompute base^(m-1) % mod for removing leftmost character
    highest_pow = 1
    for i in range(m - 1):
        highest_pow = (highest_pow * base) % mod

    # Compute initial hashes for pattern and first window
    pattern_hash = 0
    window_hash = 0
    for i in range(m):
        pattern_hash = (pattern_hash * base + ord(pattern[i])) % mod
        window_hash = (window_hash * base + ord(text[i])) % mod

    result = []
    # Slide window across text
    for i in range(n - m + 1):
        # Hash match - verify to handle collisions
        if pattern_hash == window_hash:
            # Direct comparison to confirm true match
            if text[i:i+m] == pattern:
                result.append(i)

        # Compute hash for next window if not at end
        if i < n - m:
            # Remove leftmost char, shift, add new char
            window_hash = (window_hash - ord(text[i]) * highest_pow) % mod
            # Ensure non-negative before next step
            window_hash = (window_hash * base + ord(text[i + m])) % mod
            # Python's % already handles negatives, but explicit fix is safer:
            # window_hash = (window_hash + mod) % mod

    return result

# Example
print(rabin_karp_search("abracadabra", "abra"))  # [0, 7]
print(rabin_karp_search("aaaaa", "aa"))  # [0, 1, 2, 3]

Double Hashing to Minimize Collisions

For critical applications, a single modulus is not enough. Double hashing uses two large prime moduli and only declares a match when both hashes agree, reducing collision probability from 1/M to 1/(M1*M2).

def rabin_karp_double_hash(text, pattern, base=91138233):
    """
    Double hashing version for near-zero collision probability.
    Uses two independent moduli: 10**9+7 and 10**9+9
    """
    mod1 = 10**9 + 7
    mod2 = 10**9 + 9
    n = len(text)
    m = len(pattern)
    if m > n:
        return []

    # Precompute highest powers for both moduli
    pow1 = pow(base, m-1, mod1)
    pow2 = pow(base, m-1, mod2)

    p_hash1 = p_hash2 = 0
    w_hash1 = w_hash2 = 0
    for i in range(m):
        p_hash1 = (p_hash1 * base + ord(pattern[i])) % mod1
        p_hash2 = (p_hash2 * base + ord(pattern[i])) % mod2
        w_hash1 = (w_hash1 * base + ord(text[i])) % mod1
        w_hash2 = (w_hash2 * base + ord(text[i])) % mod2

    occurrences = []
    for i in range(n - m + 1):
        if p_hash1 == w_hash1 and p_hash2 == w_hash2:
            if text[i:i+m] == pattern:  # Final verification
                occurrences.append(i)
        if i < n - m:
            w_hash1 = ((w_hash1 - ord(text[i]) * pow1) % mod1 * base + ord(text[i+m])) % mod1
            w_hash2 = ((w_hash2 - ord(text[i]) * pow2) % mod2 * base + ord(text[i+m])) % mod2

    return occurrences

print(rabin_karp_double_hash("the rolling hash algorithm rolls", "roll"))  # [4, 23]

Precomputed Powers for Multiple Queries

When you need to hash many substrings of varying lengths (e.g., for longest duplicate substring or substring equality queries), precomputing prefix hashes and powers allows O(1) hash retrieval for any substring.

class RollingHash:
    """
    Precomputed rolling hash for O(1) substring hash queries.
    Ideal for competitive programming and repeated queries.
    """
    def __init__(self, s, base=91138233, mod=10**9+7):
        self.s = s
        self.n = len(s)
        self.base = base
        self.mod = mod
        self.prefix = [0] * (self.n + 1)
        self.power = [1] * (self.n + 1)

        for i in range(self.n):
            self.prefix[i+1] = (self.prefix[i] * base + ord(s[i])) % mod
            self.power[i+1] = (self.power[i] * base) % mod

    def get_hash(self, l, r):
        """
        Get hash of substring s[l:r] (r exclusive) in O(1)
        Formula: H(l,r) = prefix[r] - prefix[l] * power[r-l]
        """
        # Ensure result is non-negative
        return (self.prefix[r] - self.prefix[l] * self.power[r - l]) % self.mod

    def equal_substrings(self, l1, r1, l2, r2):
        """Check if two substrings are equal via hash comparison"""
        if (r1 - l1) != (r2 - l2):
            return False
        return self.get_hash(l1, r1) == self.get_hash(l2, r2)

# Usage: O(1) substring comparison
rh = RollingHash("abracadabra")
print(rh.get_hash(0, 4) == rh.get_hash(7, 11))  # "abra" == "abra" -> True
print(rh.equal_substrings(0, 3, 3, 6))  # "abr" vs "aca" -> False
print(rh.get_hash(0, 3))  # Hash of "abr"

4. Step-by-Step Example

To make the rolling hash algorithm concrete, let us walk through a complete example searching for pattern P = "abc" in text T = "xabcab" using a small base b = 10 and modulus M = 101 for easy manual calculation. We will use simplified character values where 'a'=1, 'b'=2, 'c'=3, 'x'=4 for clarity. The pattern length m is 3, so we need b^(m-1) = 10^2 = 100 mod 101 = 100.

Step 1: Compute the hash of the pattern "abc". H(P) = (1*10^2 + 2*10 + 3) mod 101 = (100 + 20 + 3) mod 101 = 123 mod 101 = 22. Step 2: Compute the hash of the first window T[0:3] = "xab" = (4*100 + 1*10 + 2) mod 101 = (400 + 10 + 2) mod 101 = 412 mod 101. 101*4=404, so 412-404=8. H("xab")=8, which does not match 22, so no match at index 0.

Step 3: Roll to the next window T[1:4] = "abc". Using the recurrence: H_next = ((H_current - T[i]*b^(m-1)) * b + T[i+m]) mod M. Here, H_current=8, T[i]='x'=4, T[i+m]='c'=3. First, remove 'x': (8 - 4*100) mod 101 = (8 - 400) mod 101 = -392 mod 101. -392 + 404 = 12. Then shift: 12*10 mod 101 = 120 mod 101 = 19. Then add 'c': (19 + 3) mod 101 = 22. This matches H(P)=22, so we have a candidate match at index 1. We verify by direct comparison: T[1:4]="abc" equals P, so we record index 1.

Step 4: Roll to T[2:5] = "bca". H_current=22, outgoing 'a'=1, incoming 'a'=1. (22 - 1*100) mod 101 = (22-100) mod 101 = -78 mod 101 = 23. 23*10=230 mod 101=28 (since 202 is 2*101). 28+1=29 mod 101=29. No match. Step 5: Roll to T[3:6] = "cab". H_current=29, outgoing 'b'=2, incoming 'b'=2. (29-200) mod 101 = -171 mod 101 = 32 (since -171+202=31? Let's recompute carefully: -171 mod 101 = 31, because 101*2=202, -171+202=31). 31*10=310 mod 101=7 (303 is 3*101). 7+2=9. No match. The algorithm terminates and correctly returns [1]. This walkthrough shows how each window is computed in constant time without rehashing three characters from scratch.

Visual Trace Table

The following trace summarizes the computation, showing how the hash evolves and how verification prevents false positives even if a collision had occurred.

This example also highlights why modulus handling is critical. Without adding M to avoid negatives, languages like Python and Java would produce different intermediate results. The algorithm's correctness depends on the identity (a - b) mod M = (a mod M - b mod M + M) mod M, which guarantees a non-negative hash value consistent across all windows.

5. Complexity Analysis

Understanding the time and space complexity of the rolling hash algorithm is essential for deciding when to use it and what performance to expect in production. The analysis separates preprocessing, rolling computation, and verification costs.

Preprocessing involves computing the hash of the pattern and the first window, plus precomputing the highest power b^(m-1) mod M. This takes O(m) time and O(1) extra space beyond the input strings (or O(n) if you precompute all powers for O(1) substring queries as in the RollingHash class). Once preprocessing is complete, each of the n-m+1 windows is processed in O(1) time for the rolling update and hash comparison. Therefore, the total time to slide across the text is O(n).

The verification step is what determines the worst-case behavior. In the best and average cases, hash collisions are rare, so verification is O(1) amortized and total time remains O(n+m). In the worst case, an adversarial input or a poor choice of modulus could cause every window to have the same hash as the pattern (for example, text of all 'a's and pattern of all 'a's with a bad hash, or a crafted collision attack). In that scenario, each of the O(n) windows triggers an O(m) verification, leading to O(n*m) worst-case time, identical to naive search. However, with a large random prime modulus and a suitable base, the probability of this worst case is astronomically low, making the average case the practical expectation.

Space complexity is minimal. The basic Rabin-Karp implementation uses O(1) auxiliary space besides the input strings. The prefix-hash variant trades space for query speed, using O(n) space to store prefix hashes and powers, which enables O(1) hash retrieval for any substring. This variant is preferred when you need to answer many substring equality queries, such as in suffix array construction or finding the longest repeated substring.

In practice, the rolling hash algorithm is almost always linear. The worst case is primarily a theoretical concern or a security consideration when dealing with untrusted input that could be crafted to cause hash collisions — a hash-flooding denial-of-service attack. Using a randomized base or double hashing mitigates this risk.

6. Variations and Optimizations

The basic polynomial rolling hash is just the starting point. Several variations and optimizations adapt the rolling hash algorithm to specific constraints such as speed, collision resistance, or hardware friendliness.

Cyclic Polynomial Rolling Hash (Buzhash) is a popular alternative that uses bitwise rotation instead of multiplication by a base. It computes the hash as H = s[0]*R^(m-1) XOR s[1]*R^(m-2) XOR ... XOR s[m-1], where R is a rotation operation and s[i] are random 32-bit values assigned to each possible character. Buzhash is extremely fast because it uses only XOR and rotations, and it avoids the need for modular division. It is widely used in file chunking for deduplication systems.

Rabin Fingerprint is another variant that interprets the string as a polynomial over the Galois field GF(2) and computes the remainder modulo an irreducible polynomial. This approach is mathematically elegant and provides strong guarantees about collision probability. It is the basis for the rsync algorithm and content-defined chunking, where chunk boundaries are determined by the hash value rather than fixed offsets.

Optimizations for speed include using a modulus of the form 2^64, which leverages natural unsigned 64-bit integer overflow in languages like C++ and Rust. In this case, the modulus operation is free — overflow automatically performs mod 2^64. This is much faster than division by a prime, though it provides slightly weaker collision guarantees. Python's integers are arbitrary precision, so this optimization is less relevant there, but in compiled languages it can double performance.

Key Optimization Techniques

• Precomputed Powers: Store b^i mod M for all i to avoid repeated exponentiation. This is essential for O(1) substring hashing.
• Double or Triple Moduli: Use two or three large primes (e.g., 10^9+7, 10^9+9, 998244353) to make collisions negligible for competitive programming and cryptography-adjacent tasks.
• Randomized Base: Choose a random base between 256 and 10^9 at runtime to prevent adversarial collision attacks. This is critical for web services handling untrusted input.
• 64-bit Natural Overflow: In C++/Java, use unsigned long long overflow as modulus 2^64 for maximum speed when occasional collisions are acceptable.
• Content-Defined Chunking: Instead of fixed-size windows, declare a chunk boundary whenever hash % D == 0 for some divisor D. This creates variable-size chunks that are resilient to insertions, used in backup systems like Borg and Restic.

Choosing the right variant depends on your priorities. If you need provable low collision rates for security, use double hashing with large primes. If you need raw speed for deduplication of terabytes of data, use Buzhash or 2^64 overflow. For interview problems and general string search, the classic polynomial hash with a single prime modulus is usually sufficient and easiest to implement correctly.

7. Real-World Applications

The rolling hash algorithm is not just an academic exercise; it powers many systems you interact with daily. Its ability to efficiently fingerprint and compare sliding windows makes it indispensable across web infrastructure, databases, networking, and bioinformatics.

In web servers and content delivery networks, the rolling hash algorithm is used for duplicate content detection and caching. Search engines use it to find near-duplicate web pages (shingling) by hashing overlapping n-grams of text and comparing fingerprint sets. This helps filter out mirrored content and plagiarism. Web Application Firewalls also use rolling hashes to scan incoming payloads for known malicious signatures without slowing down request processing.

Databases and storage systems rely heavily on rolling hashes for deduplication and synchronization. The rsync protocol, which synchronizes files between computers by transferring only differences, uses a rolling checksum (Adler-32, a type of rolling hash) to find matching blocks between old and new versions of a file. Similarly, backup tools like Duplicity and cloud storage services like Dropbox use content-defined chunking with Rabin fingerprints to split files into variable-length chunks; identical chunks across different files are stored only once, saving enormous amounts of space.

In networking, the rolling hash algorithm enables efficient packet inspection and load balancing. Intrusion detection systems such as Snort use Rabin-Karp to search packet payloads for thousands of attack signatures simultaneously — a task where naive search would be far too slow. Network deduplication appliances that reduce WAN traffic also use rolling hashes to identify repeated byte sequences across packets.

In bioinformatics, searching for a gene sequence of length m in a genome of length n (where n can be 3 billion for the human genome) is a classic rolling hash application. Tools like BLAST use seeded hashing to rapidly filter candidate regions before performing expensive alignment. Without rolling hashes, genome-scale searches would be computationally infeasible.

8. Comparison with Alternatives

While the rolling hash algorithm is powerful, it is not always the best choice for string matching. Understanding its trade-offs relative to other algorithms helps you select the right tool for the job.

Naive string search is the simplest approach, checking each position character-by-character. It requires no preprocessing and has no collision risk, but its O(n*m) worst-case time makes it unsuitable for large inputs. Knuth-Morris-Pratt (KMP) guarantees O(n+m) worst-case time by using a prefix function to skip unnecessary comparisons, and it never needs verification. However, KMP is more complex to implement and cannot easily handle multiple patterns.

Boyer-Moore is often the fastest in practice for single-pattern search in natural language text because it skips ahead by multiple characters using bad-character and good-suffix heuristics. Its best case is sublinear O(n/m), but its worst case remains O(n*m) and its preprocessing is more involved. Aho-Corasick is the algorithm of choice for searching for many patterns simultaneously (e.g., thousands of keywords) by building a trie with failure links; it achieves O(n + total pattern length + number of matches) but requires significant memory for the automaton.

The rolling hash algorithm's unique advantages are its simplicity, its ability to search for multiple patterns with the same text scan (just compare the window hash against a set of pattern hashes), and its O(1) substring hash queries when using prefix hashes. Its main disadvantages are the need for collision handling and the worst-case O(n*m) time, though this is rarely encountered with good parameters.

In summary, choose the rolling hash algorithm when you need simplicity, multiple pattern search, or fast substring fingerprinting. Choose KMP when you need guaranteed worst-case linear time without probabilistic behavior. Choose Boyer-Moore for single-pattern search in large texts where sublinear performance matters, and choose Aho-Corasick when the number of patterns is very large.

9. Common Mistakes and Best Practices

Even experienced developers make subtle errors when implementing the rolling hash algorithm, leading to incorrect results, poor performance, or security vulnerabilities. Awareness of these pitfalls is crucial for production-ready code.

The most frequent mistake is incorrect handling of negative values after subtraction. In many languages, (-5) % 101 yields -5 or 96 depending on the language. In Python, it correctly yields 96, but in Java or C++ it yields -5, which breaks the hash. The safe pattern is window_hash = (window_hash - outgoing * highest_pow % mod + mod) % mod to ensure non-negativity. Another common error is forgetting to precompute b^(m-1) correctly or recomputing pow() inside the loop, which turns the O(1) update into O(m) and defeats the purpose of rolling.

Choosing a small modulus or a base that is too small is another pitfall. A modulus like 101 is fine for teaching but will cause frequent collisions in real data, degrading performance to O(n*m) due to constant verification. Always use a large prime such as 10^9+7, 10^9+9, or 2^61-1 (a Mersenne prime that allows fast modular reduction). The base should be larger than the alphabet size and ideally random; using base 256 for ASCII is common, but for lowercase letters base 91138233 or a random odd number above 256 provides better distribution.

Integer overflow is a serious issue in languages with fixed-width integers. Computing (hash * base + char) without taking modulus at each step can overflow 64-bit integers even for moderate string lengths. Always apply modulus after each multiplication and addition. In Python overflow is not an issue due to big integers, but performance suffers if numbers become huge, so frequent modulus is still important.

Best Practices Checklist

• Always verify on hash match: Never assume a hash match equals a string match; always do a direct comparison to handle collisions, especially with a single modulus.
• Use double hashing for critical correctness: If false positives are unacceptable (e.g., plagiarism detection, financial data), use two independent moduli and require both to match.
• Randomize base and modulus: To prevent hash-flooding DoS attacks where an attacker crafts inputs that all collide, pick a random base at startup and consider a random large prime.
• Precompute powers once: Compute the power array up to n before the main loop; never call pow(base, m-1, mod) inside the sliding window loop.
• Test edge cases: Verify behavior when pattern is empty, pattern is longer than text, text and pattern are identical, and when the text contains repeated characters.
• Profile before optimizing: For most applications, a single modulus with base 91138233 is fast enough; only switch to 2^64 overflow or Buzhash if profiling shows hashing is the bottleneck.

Finally, remember that the rolling hash algorithm is probabilistic. Document this assumption for future maintainers and include the verification step even if you believe collisions are impossible. A well-implemented rolling hash is both fast and reliable, but only when these best practices are followed consistently.

10. Interview Questions

The rolling hash algorithm is a favorite in technical interviews because it tests understanding of hashing, modular arithmetic, string manipulation, and complexity analysis. Below are common questions with guidance on how to approach them.

Q1: Implement Rabin-Karp to Find All Occurrences of a Pattern

This is the most direct question. The interviewer expects you to implement the rolling hash update correctly, handle modulus, and verify matches. Start by explaining the polynomial hash formula, then write the code for initial hash computation and the O(1) rolling step. Emphasize the need for verification and discuss the choice of base and modulus. A strong answer includes handling edge cases and mentions double hashing as an extension. Complexity should be stated as O(n+m) average and O(n*m) worst case.

Q2: Find the Longest Duplicate Substring in a String

Given a string s, find the longest substring that appears at least twice. This problem combines rolling hash with binary search. The approach is to binary search on the length L: for a given L, compute the hash of every substring of length L using a rolling hash and store them in a hash set; if any hash appears twice (with verification), then a duplicate of length L exists, so search for longer L, otherwise search shorter. The rolling hash enables O(n) checking per L, and binary search adds O(log n), for total O(n log n) average time. This question tests whether you can apply rolling hash beyond simple pattern search.

Q3: How Would You Detect Duplicate Documents Among Millions of Web Pages?

This system design question explores shingling with rolling hashes. The solution involves breaking each document into overlapping k-shingles (e.g., 5-grams), hashing each shingle with a rolling hash, and then selecting a subset of hashes (e.g., via min-hashing) to represent the document fingerprint. Two documents are considered near-duplicates if their fingerprint sets have high Jaccard similarity. The rolling hash makes shingle hashing efficient, and the discussion should cover choosing k, handling collisions, and scaling to distributed computation. This demonstrates real-world application of the algorithm.

Q4: What Are Hash Collisions and How Do You Handle Them? Can an Attacker Exploit Your Hash?

Here the interviewer probes deeper understanding of the probabilistic nature of hashing. Explain that collisions occur when two different strings map to the same hash due to the finite modulus, and that the probability is roughly 1/M for a random prime M. Handling involves verification by direct comparison and using double hashing to reduce probability to 1/(M1*M2). For security, discuss hash-flooding attacks where an adversary crafts many strings with the same hash to degrade performance to O(n*m), and mitigation via randomized base/modulus or using a cryptographic hash for untrusted input. This question distinguishes candidates who understand both theory and practical security.

Q5: Compare Rolling Hash with KMP and Boyer-Moore — When Would You Choose Each?

This comparison question tests breadth of knowledge in string algorithms. A good answer uses a table or structured comparison: rolling hash is best for multiple patterns and substring fingerprinting with O(n+m) average but probabilistic; KMP guarantees O(n+m) worst case and is deterministic but handles only one pattern; Boyer-Moore is fastest in practice for natural language due to skipping but has complex preprocessing. Mention that rolling hash is simplest to implement and extends to 2D pattern search (e.g., image search), while Aho-Corasick is superior for thousands of patterns. Conclude with a decision framework based on number of patterns, worst-case guarantees, and implementation time.