String Hashing Technique: Efficient String Processing

1. Introduction and Core Concepts

The string hashing technique is one of the most powerful and versatile tools in the field of string algorithms, enabling developers to process, compare, and search textual data with remarkable efficiency. At its core, the string hashing technique transforms a string of arbitrary length into a compact numerical representation, known as a hash value or fingerprint. This transformation allows algorithms to compare strings by comparing integers instead of character-by-character, which dramatically reduces processing time for large datasets.

Why does the string hashing technique matter so much in modern computing? Consider the scale of string processing today: search engines index billions of web pages, DNA sequencing pipelines analyze strings containing millions of base pairs, and plagiarism detection systems compare vast document corpora. A naive character-by-character comparison for each operation would be prohibitively slow. The string hashing technique provides a near constant-time mechanism to answer critical questions such as: Are these two substrings equal? Does a pattern occur in a text? How many distinct substrings does a string contain?

The fundamental idea behind the string hashing technique is to map strings to integers using a deterministic mathematical function. A good hash function should be fast to compute, distribute hash values uniformly to minimize collisions, and allow efficient computation for substrings. The most widely used approach is polynomial rolling hashing, which treats a string as a number in a large base. For example, the string "abc" can be interpreted as 1*P^2 + 2*P^1 + 3*P^0 where P is a chosen base and characters are mapped to numbers (a->1, b->2, etc.). By performing all operations modulo a large prime number, we keep hash values within a manageable range while preserving the ability to compare strings efficiently.

The Core Properties of an Effective Hash Function

An effective string hashing technique must balance three competing properties: determinism, efficiency, and collision resistance. Determinism ensures the same string always produces the same hash value, which is essential for correctness. Efficiency requires that hash computation be fast, ideally linear in the length of the string during preprocessing and constant time for subsequent queries. Collision resistance means different strings should rarely produce the same hash value, although collisions can never be entirely eliminated when mapping an infinite set of strings to a finite set of integers.

To achieve this balance, practitioners carefully select two parameters: the base (often denoted as P or B) and the modulus (M). The base is typically a small prime larger than the alphabet size, such as 31 or 91138233 for lowercase English letters, while the modulus is a large prime like 10^9+7 or 10^9+9. Using a large prime modulus ensures that the hash values are uniformly distributed and that modular arithmetic properties can be leveraged for fast substring hash computation. Understanding these core concepts is the foundation for mastering the entire string hashing technique.

2. How It Works

The string hashing technique most commonly uses polynomial rolling hash, which provides an elegant way to compute hashes for all prefixes of a string and then derive the hash of any substring in constant time. Let s = s[0] s[1] ... s[n-1] be a string of length n. We define the hash of the prefix ending at index i as H[i+1] = (s[0]*P^(i) + s[1]*P^(i-1) + ... + s[i]*P^0) mod M. More efficiently, it is computed iteratively as H[0] = 0 and H[i+1] = (H[i] * P + val(s[i])) mod M, where val(s[i]) is the numeric value of the character.

This iterative definition is crucial because it allows incremental construction. Once we have precomputed the prefix hash array H and the powers of P (pow[i] = P^i mod M), we can compute the hash of any substring s[l..r] (inclusive) using the formula: hash(l, r) = (H[r+1] - H[l] * pow[r-l+1]) mod M. The subtraction may yield a negative number, so we adjust by adding M before taking the final modulo. This formula is derived from the fact that H[r+1] contains the hash of s[0..r] and H[l] contains the hash of s[0..l-1]; by shifting H[l] to align with H[r+1], we can isolate the contribution of the substring.

The power of this mechanism lies in its ability to answer substring equality queries in O(1) time after O(n) preprocessing. Without hashing, comparing two substrings of length L would require O(L) time. With the string hashing technique, we simply compute their integer hashes and compare the integers. If the hashes differ, the substrings are definitely different. If the hashes are equal, the substrings are equal with high probability, assuming a good choice of modulus and base. The probability of a collision can be made negligible by using double hashing or 64-bit random moduli.

Polynomial Rolling Hash in Detail

To illustrate, consider the alphabet mapping where 'a' = 1, 'b' = 2, ..., 'z' = 26, base P = 31, and modulus M = 10^9+7. For the string "abac", the prefix hashes are computed as follows: H[0]=0, H[1]=(0*31+1)=1, H[2]=(1*31+2)=33, H[3]=(33*31+1)=1024, H[4]=(1024*31+3)=31747. The power array is pow[0]=1, pow[1]=31, pow[2]=961, pow[3]=29791. To get the hash of substring "ba" (indices 1 to 2), we compute (H[3] - H[1]*pow[2]) mod M = (1024 - 1*961) = 63. Directly hashing "ba" gives 2*31+1=63, confirming the formula.

This rolling property is what makes the string hashing technique so efficient for sliding window problems. When we move a window of fixed length across a text, we do not need to recompute the hash from scratch. Instead, we can update the hash by removing the contribution of the outgoing character and adding the incoming character, all in constant time. This is the core principle behind the Rabin-Karp string matching algorithm, which uses hashing to find pattern occurrences in linear expected time.

3. Implementation

Implementing the string hashing technique in Python requires careful handling of modular arithmetic, precomputation, and negative modulo results. The following examples demonstrate a complete, production-ready implementation with detailed comments and collision-aware design. All code is written to be clear, efficient, and easily adaptable to competitive programming and system design contexts.

The first implementation shows the basic building blocks: computing prefix hashes and powers, and querying substring hashes. This is the foundation upon which all other applications are built.

MOD = 10**9 + 7
BASE = 91138233  # Large random base > alphabet size
# Alternative common choice: BASE = 31 for lowercase letters

def build_hash(s, base=BASE, mod=MOD):
    """
    Build prefix hash and power arrays for string s.
    H[i] = hash of s[0:i] (first i characters)
    pow[i] = base^i % mod
    Time: O(n), Space: O(n)
    """
    n = len(s)
    prefix = [0] * (n + 1)
    power = [1] * (n + 1)
    
    for i in range(n):
        # val maps 'a' -> 1, 'b' -> 2, ... works for any ascii
        val = ord(s[i])  # use full ascii value for generality
        prefix[i + 1] = (prefix[i] * base + val) % mod
        power[i + 1] = (power[i] * base) % mod
        
        # Example of escaped comparison inside code: 
        # if prefix[i + 1] < 0: prefix[i + 1] += mod
    return prefix, power

def get_hash(prefix, power, l, r, mod=MOD):
    """
    Get hash of substring s[l:r] inclusive, 0-indexed.
    Requires 0 <= l <= r < n
    Formula: H[r+1] - H[l] * pow[r-l+1]
    """
    # Ensure l <= r and indices are valid
    if l > r:
        return 0
    raw = prefix[r + 1] - (prefix[l] * power[r - l + 1] % mod)
    # Handle negative modulo correctly
    if raw < 0:
        raw += mod
    return raw % mod

# Example usage
s = "abacaba"
pref, pw = build_hash(s)
# Hash of "bac" (indices 1 to 3)
print(get_hash(pref, pw, 1, 3))  # hash of "bac"
# Hash of "aba" (indices 0 to 2) vs (4 to 6) should be equal
print(get_hash(pref, pw, 0, 2) == get_hash(pref, pw, 4, 6))  # True

While a single modulus is sufficient for many cases, critical applications require double hashing to reduce collision probability to near zero. The next example implements double hashing with two independent large prime moduli. Two substrings are considered equal only if both hashes match, which reduces collision probability from 1/M to 1/(M1*M2).

MOD1 = 10**9 + 7
MOD2 = 10**9 + 9
BASE = 91138233

def build_double_hash(s, base=BASE):
    """Build double hash tables for strong collision resistance."""
    n = len(s)
    pref1 = [0] * (n + 1)
    pref2 = [0] * (n + 1)
    pow1 = [1] * (n + 1)
    pow2 = [1] * (n + 1)
    
    for i in range(n):
        val = ord(s[i])
        pref1[i + 1] = (pref1[i] * base + val) % MOD1
        pref2[i + 1] = (pref2[i] * base + val) % MOD2
        pow1[i + 1] = (pow1[i] * base) % MOD1
        pow2[i + 1] = (pow2[i] * base) % MOD2
    return (pref1, pow1), (pref2, pow2)

def get_double_hash(p1, p2, l, r):
    """Return tuple (h1, h2) for substring s[l:r]."""
    pref1, pow1 = p1
    pref2, pow2 = p2
    h1 = (pref1[r + 1] - pref1[l] * pow1[r - l + 1]) % MOD1
    h2 = (pref2[r + 1] - pref2[l] * pow2[r - l + 1]) % MOD2
    # Python's % already handles negatives, but explicit check:
    # if h1 < 0: h1 += MOD1
    # if h2 < 0: h2 += MOD2
    return (h1, h2)

def are_equal(p1, p2, l1, r1, l2, r2):
    """Check if s[l1:r1] == s[l2:r2] in O(1) with double hash."""
    # Length must match first: if (r1 - l1) != (r2 - l2): return False
    if (r1 - l1) != (r2 - l2):
        return False
    return get_double_hash(p1, p2, l1, r1) == get_double_hash(p1, p2, l2, r2)

The string hashing technique truly shines in pattern matching. The following Rabin-Karp implementation finds all occurrences of a pattern in a text using rolling hashes, achieving linear expected time without the complex failure function of KMP.

def rabin_karp(text, pattern, base=31, mod=10**9+7):
    """
    Find all occurrences of pattern in text using string hashing technique.
    Returns list of starting indices.
    """
    n, m = len(text), len(pattern)
    if m > n or m == 0:
        return []
    
    # Precompute hash for pattern and first window of text
    pat_hash = 0
    win_hash = 0
    power = 1  # base^(m-1) for rolling update
    
    for i in range(m):
        pat_hash = (pat_hash * base + ord(pattern[i])) % mod
        win_hash = (win_hash * base + ord(text[i])) % mod
        if i < m - 1:
            power = (power * base) % mod
    
    occurrences = []
    for i in range(n - m + 1):
        if win_hash == pat_hash:
            # Hash match - verify to handle collision (optional but safe)
            if text[i:i+m] == pattern:
                occurrences.append(i)
        
        # Roll hash to next window: remove text[i], add text[i+m]
        if i < n - m:
            # win_hash = (win_hash - ord(text[i])*power) * base + ord(text[i+m])
            win_hash = (win_hash - ord(text[i]) * power) % mod
            win_hash = (win_hash * base + ord(text[i + m])) % mod
            if win_hash < 0:
                win_hash += mod
    return occurrences

# Example: find "aba" in "abacababa"
print(rabin_karp("abacababa", "aba"))  # Output: [0, 5, 7] (depending on verification)

Finally, the string hashing technique enables elegant solutions to counting distinct substrings, a classic problem where naive enumeration would be O(n^3). By inserting all substring hashes into a set, we can count distinct substrings in O(n^2) time with hashing, which is optimal for many practical constraints.

def count_distinct_substrings(s, base=91138233, mod=10**9+7):
    """
    Count distinct substrings using string hashing technique.
    Uses set of hashes to avoid storing actual substrings.
    Time: O(n^2) average, Space: O(n^2) for hash set
    """
    n = len(s)
    pref, pw = build_hash(s, base, mod)
    seen = set()
    
    for l in range(n):
        for r in range(l, n):
            # For each substring s[l:r] inclusive
            h = get_hash(pref, pw, l, r, mod)
            # To handle collisions, could store (h, substring length) or use double hash
            # if h < 0: h += mod  # already handled in get_hash
            seen.add(h)
            # For perfect accuracy with double hash:
            # seen.add((h1, h2))
    
    return len(seen)

def longest_common_prefix_hash(s, i, j, pref, pw, mod=10**9+7):
    """
    Find LCP of suffixes starting at i and j using binary search + hashing.
    Time: O(log n) per query after O(n) preprocessing.
    """
    n = len(s)
    low, high = 0, min(n - i, n - j)
    ans = 0
    while low <= high:
        mid = (low + high) // 2
        # Check if s[i:i+mid] == s[j:j+mid]
        if mid == 0:
            ans = 0
            low = mid + 1
            continue
        h1 = get_hash(pref, pw, i, i + mid - 1, mod)
        h2 = get_hash(pref, pw, j, j + mid - 1, mod)
        if h1 == h2:
            ans = mid
            low = mid + 1  # try longer
        else:
            high = mid - 1  # try shorter
    return ans

4. Step-by-Step Example

To solidify understanding of the string hashing technique, let us walk through a complete concrete example. We will use the string s = "ababa", base P = 31, modulus M = 1,000,000,007, and character mapping 'a' = 1, 'b' = 2. This small example allows us to compute all values by hand and verify the substring hash formula.

Step 1: Precompute prefix hashes and powers. We initialize H[0] = 0 and pow[0] = 1. Then iteratively compute: H[1] = (0*31 + 1) % M = 1 for 'a', pow[1] = 31. H[2] = (1*31 + 2) = 33 for "ab", pow[2] = 961. H[3] = (33*31 + 1) = 1024 for "aba", pow[3] = 29791. H[4] = (1024*31 + 2) = 31746 for "abab", pow[4] = 923521. H[5] = (31746*31 + 1) = 984127 for "ababa", pow[5] = 28629151. These arrays are built once in O(n) time.

Step 2: Query substring hashes. Suppose we want to check if substring "aba" at position 0 (indices 0-2) equals substring "aba" at position 2 (indices 2-4). Using the formula hash(l,r) = H[r+1] - H[l]*pow[r-l+1]. For l=0, r=2: hash = H[3] - H[0]*pow[3] = 1024 - 0 = 1024. For l=2, r=4: hash = H[5] - H[2]*pow[3] = 984127 - 33*29791 = 984127 - 983103 = 1024. The hashes match, indicating the substrings are equal, which they are.

Step 3: Test a negative case. Compare "aba" (0-2) with "bab" (1-3). Hash of "bab" is H[4] - H[1]*pow[3] = 31746 - 1*29791 = 1955. Direct computation of "bab" is 2*31^2 + 1*31 + 2 = 2*961 + 31 + 2 = 1955, which differs from 1024, so the technique correctly identifies them as different. This verification shows how the string hashing technique reduces substring comparison to integer arithmetic.

Collision Handling in the Example

In our small modulus example, collisions are unlikely but possible with larger strings. If we had used a tiny modulus like M=100, we would see collisions: "ab" hash 33 and "aa" with different base might collide. This is why real implementations use large primes like 10^9+7 and often double hashing. In the double hashing variant, we would compute both hashes independently; only if both match do we declare equality. For "ababa", using MOD1=10^9+7 and MOD2=10^9+9, the pair of hashes for "aba" would be (1024, 1024) in both cases, providing extremely high confidence.

This step-by-step process demonstrates the full lifecycle of the string hashing technique: O(n) preprocessing to build prefix and power arrays, followed by O(1) queries for any substring. The same precomputation can answer thousands of queries, making it ideal for problems requiring many substring comparisons, such as finding the longest palindromic substring or determining the longest repeated substring.

5. Complexity Analysis

Understanding the time and space complexity of the string hashing technique is essential for selecting it appropriately and for analyzing its performance in interviews and production systems. The technique offers excellent average-case performance, with preprocessing that is linear and queries that are constant time, but it is important to distinguish between expected performance and worst-case behavior due to collisions.

The preprocessing phase, which builds the prefix hash array and power array, requires O(n) time and O(n) space where n is the length of the string. Each of the n characters is processed once, performing a constant number of modular multiplications and additions. The space overhead is two arrays of length n+1, each storing integers modulo M. This preprocessing is a one-time cost that amortizes over many queries, making the technique highly efficient when many substring operations are needed.

After preprocessing, computing the hash of any substring takes O(1) time using the formula with one multiplication, one subtraction, and one modulo operation. Comparing two substrings for equality also takes O(1) time, as it involves comparing two integers (or two pairs of integers for double hashing). Pattern matching with Rabin-Karp using rolling hashes takes O(n + m) expected time where n is text length and m is pattern length, because each window's hash is updated in O(1) and only hash matches require verification.

The worst-case time complexity can degrade to O(n*m) for Rabin-Karp if there are many spurious hash collisions and every window requires verification, or if an adversary crafts inputs to force collisions with a fixed modulus. However, with a large random modulus or double hashing, the probability of this worst case is astronomically low. Using Python's built-in hash randomization or a 64-bit random base further mitigates adversarial attacks.

* Worst-case O(1) for hash comparison, but O(L) if verification is needed to handle collisions where L is substring length. With double hashing, verification is rarely needed.

Space complexity is consistently O(n) for the prefix and power arrays, plus O(1) auxiliary space for queries. For double hashing, space doubles to O(2n) but remains linear. When counting distinct substrings, the hash set can grow to O(n^2) in the worst case, which dominates the space usage for that specific application. Overall, the string hashing technique provides an excellent trade-off between time and space for most string processing tasks.

6. Variations and Optimizations

While the basic polynomial rolling hash is powerful, several variations and optimizations of the string hashing technique have been developed to address specific challenges such as collision resistance, performance on large alphabets, and support for different operations. Understanding these variants allows engineers to tailor the technique to their exact requirements.

Double hashing is the most common optimization for improving collision resistance. Instead of a single modulus, two large independent primes (e.g., 10^9+7 and 10^9+9) are used, and a substring is considered equal only if both hashes match. The collision probability drops from roughly 1/M to 1/(M1 * M2), which is effectively zero for practical purposes. An even stronger variant uses a 64-bit random modulus, such as 2^64 with natural overflow (using Python's built-in overflow simulation or using unsigned 64-bit integers in other languages), which leverages hardware efficiency while providing excellent distribution.

Another important variation is the choice of base. For lowercase English letters, base 31 or 91138233 are popular, but for larger alphabets (Unicode, DNA sequences with 4 characters), the base should be larger than the alphabet size to ensure injectivity before modulo. Some implementations use a random base between 256 and 10^9 to prevent adversarial collision attacks, where an attacker crafts strings that collide under a fixed base and modulus to degrade performance to worst-case. Randomizing the base at runtime is a standard best practice in competitive programming and security-sensitive applications.

For problems requiring palindrome detection, the string hashing technique can be extended with forward and reverse hashes. By building prefix hashes for both the string and its reverse, we can check if any substring is a palindrome in O(1) time by comparing the forward hash of s[l..r] with the reverse hash of the corresponding segment in the reversed string. This enables O(n log n) or even O(n) solutions for longest palindromic substring when combined with binary search.

Advanced Optimizations

Beyond double hashing, there are more advanced optimizations. One is using precomputed factorials and modular inverses for alternative hash definitions that support O(1) substring hash with different polynomial formulations. Another is using polynomial hashing with multiple bases in a single modulus, which can be faster than double modulus due to fewer modulo operations. For very long strings (millions of characters), using PyPy's fast I/O and array('l') or numpy for storage can reduce constant factors.

Segment tree or Fenwick tree combined with hashing allows for dynamic strings where characters can be updated. In this variant, the hash of the entire string is maintained in a tree structure where each node stores the hash of its segment, allowing point updates and substring hash queries in O(log n) time. This is invaluable for problems with online queries and modifications, such as dynamic palindrome checking or versioned document comparison.

7. Real-World Applications

The string hashing technique is not merely an academic exercise; it powers critical infrastructure across web servers, databases, networks, and bioinformatics. Its ability to quickly compare and index textual data makes it indispensable in systems that handle massive string datasets.

In web servers and content delivery networks, the string hashing technique is used for caching and deduplication. URLs, HTTP headers, and file contents are hashed to generate cache keys, allowing O(1) lookup of cached responses. Rabin-Karp style rolling hashes are used in rsync and Dropbox's delta synchronization to identify changed blocks between file versions without transmitting the entire file. By hashing fixed-size blocks and comparing hashes, only modified blocks are transferred, saving enormous bandwidth.

Databases heavily rely on string hashing for indexing and query optimization. Hash indexes use the technique to map string keys (like email addresses or product names) to bucket locations, enabling fast point lookups. In distributed databases, consistent hashing—a variant of the string hashing technique—distributes data across shards by hashing shard keys, ensuring even load distribution and minimal data movement when nodes are added or removed. PostgreSQL and MySQL both support hash indexes for string columns where equality checks dominate.

In cybersecurity and networks, the string hashing technique underpins intrusion detection systems and plagiarism detection. Network intrusion systems hash packet payloads to quickly match against signatures of known attacks. Plagiarism detectors like Turnitin and Moss hash overlapping k-grams (substrings of length k) of documents and compare hash sets to find similar passages, even when text is slightly modified. This approach scales to millions of documents because hash comparison is far faster than direct text comparison.

In bioinformatics, the string hashing technique accelerates DNA sequence analysis. Genomes are strings over the alphabet {A, C, G, T}, often billions of characters long. Hashing k-mers (substrings of length k) allows rapid alignment of reads to reference genomes, as in the BLAST algorithm. Instead of comparing sequences character by character, hashed k-mers are indexed and looked up in constant time, enabling the analysis of massive genomic datasets that would otherwise be computationally infeasible.

8. Comparison with Alternatives

While the string hashing technique is highly effective, it is not the only approach for string processing. Understanding how it compares to alternatives like brute force, Knuth-Morris-Pratt (KMP), Trie, and Suffix Array helps in selecting the right tool for a given problem. Each method has distinct trade-offs in preprocessing time, query time, space, and handling of collisions or ordering.

Brute force comparison is the simplest alternative, checking each character sequentially. It requires no preprocessing and no extra space, but comparing two substrings of length L takes O(L) time, and searching for a pattern of length m in text of length n takes O(n*m) worst-case time. It is only suitable for very small strings or one-off comparisons where preprocessing overhead is not justified.

KMP is a deterministic pattern matching algorithm that guarantees O(n + m) worst-case time with O(m) preprocessing and no collisions. Unlike the string hashing technique, KMP never requires verification and is immune to adversarial inputs. However, KMP is specialized for pattern matching and does not support general substring equality queries or counting distinct substrings. It also requires building a failure function, which is more complex to implement than hashing.

Tries and suffix arrays are data structures that excel at different tasks. A Trie provides O(L) substring search where L is query length and supports prefix queries and autocomplete, but it requires O(total characters) space and is not efficient for arbitrary substring equality. Suffix arrays with LCP arrays can answer many string queries in O(log n) time and support lexicographic ordering, but they require O(n log n) construction time and O(n) space, making them heavier than hashing for simple equality checks.

In practice, the string hashing technique is often the best choice when you need to answer many substring equality queries, count distinct substrings, or implement a simple yet fast pattern matcher. For security-critical or worst-case guarantee scenarios, KMP or suffix arrays may be preferred. Many modern systems combine approaches, using hashing for fast filtering and exact methods for verification, achieving both speed and correctness.

9. Common Mistakes and Best Practices

Even experienced developers can introduce subtle bugs when implementing the string hashing technique. Awareness of common pitfalls and adherence to best practices ensures correctness, performance, and resistance to collisions and adversarial attacks.

One of the most frequent mistakes is incorrect handling of negative modulo results. In Python, the expression (H[r+1] - H[l] * pow[r-l+1]) % MOD correctly handles negatives because Python's modulo yields a non-negative result, but in many languages like C++ or Java, the result can be negative. Forgetting to add MOD before the final modulo leads to incorrect hash values and false negatives. Always write hash = (H[r+1] - H[l] * pow[len] % MOD + MOD) % MOD to be safe across languages.

Another common error is choosing a small or non-prime modulus, or a base smaller than the alphabet size. Using modulus 2^31 or 1000000000 (non-prime) leads to poor distribution and many collisions due to non-uniform mapping. Similarly, using base 26 for lowercase letters can cause collisions for anagrams before modulo. Best practice is to use large primes like 10^9+7 and 10^9+9, and a base that is a random large odd number greater than alphabet size, ideally between 256 and 10^9.

Off-by-one errors in prefix array indexing are also prevalent. The prefix array is typically size n+1 where prefix[0]=0 and prefix[i] corresponds to first i characters. Querying substring [l, r] inclusive requires prefix[r+1] and prefix[l], not prefix[r] and prefix[l-1]. Mixing inclusive and exclusive bounds results in wrong hashes that are hard to debug. Always test with small examples like "a" and "ab" to verify indexing.

Best Practices for Robust Implementation

• Use Double Hashing for Critical Applications: For interview problems and production systems where correctness is paramount, implement double hashing with two independent moduli. The overhead is minimal and collision probability becomes negligible.
• Randomize Base and Modulus: To prevent hack tests that craft collision-heavy inputs, randomize base at runtime using Python's random module. This is standard in competitive programming.
• Precompute Powers Once: Compute power array up to maximum string length once and reuse it for all queries, rather than recomputing powers per query.
• Verify on Hash Match for Pattern Search: In Rabin-Karp, always verify character-by-character when hashes match to guarantee correctness, unless using double hashing with extremely low collision probability and performance is critical.
• Handle Large Strings with 64-bit Hashing: For strings longer than 10^6, consider using Python's built-in hash with 64-bit overflow simulation or using library like hashlib for cryptographic strength if needed, though polynomial hash is usually sufficient.
• Test Edge Cases: Test empty string, single character, all same characters, and very long strings to ensure modulo and indexing handle all scenarios.

Finally, avoid using string hashing technique where exact lexicographic ordering is required. Hashes do not preserve order, so sorting strings by hash value is meaningless. For ordering, use suffix arrays or direct string comparison. By following these best practices, you can leverage the string hashing technique safely and efficiently.

10. Interview Questions

Mastery of the string hashing technique is frequently tested in technical interviews for software engineering roles. Below are common interview questions that assess understanding of the technique, along with guidance on how to approach them effectively.

Question 1: Check if Two Substrings Are Equal

Problem: Given a string s up to 10^5 characters and up to 10^5 queries, each query gives indices (l1, r1, l2, r2) and asks if s[l1..r1] == s[l2..r2]. How would you answer each query efficiently?

Approach: This is the classic use case for the string hashing technique. Preprocess the string in O(n) to build prefix hash and power arrays. For each query, compute hash(l1, r1) and hash(l2, r2) in O(1) and compare. If lengths differ, immediately return false. For robustness, use double hashing. Complexity is O(n + q) overall, where q is number of queries. Be sure to explain the formula and handle negative modulo, and discuss collision probability.

Question 2: Find Duplicate Substrings or Longest Repeated Substring

Problem: Find the longest substring that appears at least twice in a string s.

Approach: Use binary search on length L combined with the string hashing technique. For a given L, compute hashes of all substrings of length L in O(n) using rolling hash, insert into a hash set, and check for duplicates. If duplicate exists, try larger L; otherwise try smaller L. This yields O(n log n) time. Alternatively, hash all substrings and sort hashes. Mention that suffix array is an alternative but hashing is simpler to implement under interview time constraints.

Question 3: Rabin-Karp Pattern Matching

Problem: Implement strStr() to find the first occurrence of pattern p in text t. Explain time complexity and how you handle collisions.

Approach: Describe the string hashing technique for Rabin-Karp: compute hash of pattern and rolling hash of text windows. Expected O(n + m) time. Emphasize the rolling update formula and the need to verify matches to handle collisions. Discuss worst-case O(n*m) and how double hashing mitigates it. Provide Python code with base and modulus choices, and explain why you chose them.

Question 4: Count Distinct Substrings

Problem: Given a string s, count the number of distinct substrings.

Approach: Enumerate all O(n^2) substrings, compute each substring's hash in O(1) using prefix hashes, and insert into a set. Answer is size of set. Time O(n^2) average, space O(n^2). For n up to 2000 this passes; for larger n, mention suffix array + LCP as O(n log n) alternative. Discuss using double hashing to avoid collisions affecting count.

Question 5: Palindrome Checking with Hashing

Problem: Given many queries asking if substring s[l..r] is a palindrome, answer each in O(1) after preprocessing.

Approach: Build forward hash for s and reverse hash for reversed string rev = s[::-1]. Substring s[l..r] is palindrome if its forward hash equals the hash of its reverse, which corresponds to rev[n-1-r .. n-