Rabin-Karp String Search: Algorithm Analysis and Code

Introduction and Core Concepts

Rabin-Karp string search is a powerful string-searching algorithm that leverages hashing to efficiently locate a pattern within a larger text. Unlike naive approaches that compare characters one by one at every position, rabin-karp string search transforms the problem into a numeric one: it computes hash values for the pattern and for substrings of the text, comparing hashes first and only verifying character-by-character when hashes match. This filtering mechanism dramatically reduces the number of expensive string comparisons in the average case.

Developed in 1987 by Richard M. Karp and Michael O. Rabin, the algorithm was originally designed to solve the problem of finding a single pattern efficiently, but its true strength emerges when searching for multiple patterns simultaneously. Because it is based on hashing, the same rolling hash infrastructure can be reused to search for many patterns in a single pass over the text, making it fundamentally different from character-comparison algorithms like Knuth-Morris-Pratt (KMP) or Boyer-Moore.

At its core, rabin-karp string search relies on three key ideas: a hash function that maps strings to integers, a rolling hash technique that allows the hash of the next text window to be computed in constant time from the previous one, and a collision resolution strategy that verifies matches to handle hash collisions. The choice of hash function is critical. Most implementations use a polynomial rolling hash, often called the Rabin fingerprint, which treats a string as a number in a base-b number system modulo a large prime. Understanding these core concepts is essential for appreciating both the elegance and the trade-offs of the algorithm.

Why Hashing Matters for String Search

String comparison is expensive when patterns are long. A naive algorithm might compare up to m characters at each of n-m+1 positions, leading to O(n*m) worst-case time. Hashing reduces each substring comparison to an integer comparison, which is O(1). Only when two hashes are equal do we pay the cost of a full verification. If the hash function distributes values uniformly and collisions are rare, the algorithm performs near-linear time.

Another reason rabin-karp string search matters is its conceptual simplicity and adaptability. It does not require complex preprocessing tables like KMP's prefix function or Boyer-Moore's bad-character and good-suffix tables. Its logic is intuitive: hash, roll, compare. This makes it an excellent teaching tool for hashing, modular arithmetic, and randomized algorithms, while also being practical enough for production systems.

How It Works

The rabin-karp string search algorithm operates by sliding a window of length m, where m is the pattern length, across the text of length n. Before the search begins, it computes the hash value of the pattern, commonly denoted as hash(P), and the hash value of the first window of text, hash(T[0..m-1]). If these two hashes differ, the pattern cannot be at position 0, and the algorithm moves to the next window without any character comparison.

The ingenuity of the algorithm lies in how it computes the hash of the next window. Recomputing the hash from scratch for every window would be O(m) per window and offer no advantage over the naive approach. Instead, Rabin-Karp uses a rolling hash. For a polynomial hash defined as H = c0*b^(m-1) + c1*b^(m-2) + ... + c(m-1)*b^0 mod q, where b is a base and q is a large prime modulus, the hash of T[i+1..i+m] can be derived from the hash of T[i..i+m-1] in constant time. The formula removes the contribution of the outgoing character, multiplies by the base to shift all remaining characters, and adds the incoming character.

Formally, the rolling update is: hash_next = ( (hash_current - T[i]*b^(m-1) ) * b + T[i+m] ) mod q. To make this efficient, the value b^(m-1) mod q is precomputed once. All operations are performed modulo q to keep numbers small and prevent integer overflow. When hash(P) equals hash(T[i..i+m-1]), the algorithm performs a direct string comparison to confirm whether this is a true match or a spurious hit caused by a hash collision. This verification step is essential because two different strings can have the same hash value modulo q.

The Role of the Modulus and Base

The choice of modulus q and base b directly affects performance and correctness. The base is typically the size of the alphabet, such as 256 for extended ASCII or 26 for lowercase letters, or a small prime like 101. The modulus should be a large prime to minimize collisions and distribute hash values evenly. A larger modulus reduces the collision probability but increases the risk of overflow in languages with fixed-size integers, though Python handles arbitrary-precision integers naturally. In practice, a modulus like 10^9+7 or a random large prime is common.

If q is too small, collisions become frequent, and the algorithm degrades to performing a verification at many positions, approaching O(n*m) worst-case time. If q is very large, collisions become negligible, and the algorithm behaves like a randomized algorithm with expected linear time. Some theoretical variants even use multiple moduli to make the collision probability vanishingly small without explicit verification, but most practical implementations keep the single-modulus plus verification approach for simplicity.

Handling Hash Collisions

A hash collision occurs when two different strings produce the same hash value. In rabin-karp string search, a collision leads to a spurious hit: the algorithm thinks it may have found the pattern and triggers a verification that ultimately fails. The correctness of the algorithm is never compromised because verification always checks the actual characters, but frequent collisions hurt performance. The expected number of collisions is n/q, so choosing a large prime q makes collisions extremely rare for typical text sizes.

Implementation

Implementing rabin-karp string search in Python requires careful handling of modular arithmetic, especially for negative values after subtraction. Python's modulo operator handles negatives correctly, but explicitly adding the modulus ensures clarity and portability. The following implementations progress from a basic version to a robust, production-ready variant that supports multiple pattern searches.

The first implementation demonstrates the core rolling hash logic for a single pattern. It includes detailed comments explaining each step, from precomputing the high-order base power to the rolling update and verification.

def rabin_karp_single(text, pattern, base=256, mod=101):
    """
    Basic Rabin-Karp for single pattern search.
    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 rolling hash
    h = 1
    for i in range(m - 1):
        h = (h * base) % mod

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

    result = []
    # Slide window over text
    for i in range(n - m + 1):
        # Hash match - verify to handle collisions
        if pattern_hash == window_hash:
            # Character-by-character verification
            if text[i:i+m] == pattern:
                result.append(i)

        # Compute hash for next window
        if i < n - m:
            window_hash = (window_hash - ord(text[i]) * h) % mod
            window_hash = (window_hash * base + ord(text[i + m])) % mod
            # Ensure non-negative (Python handles this, but explicit)
            window_hash = (window_hash + mod) % mod

    return result

The second implementation improves robustness by using a larger prime modulus to reduce collisions and by encapsulating the hash computation in helper functions. This version is more readable and easier to adapt for different alphabets or data types.

def rabin_karp_robust(text, pattern, base=256, mod=1000000007):
    """
    Robust Rabin-Karp with large prime modulus.
    Uses helper functions for clarity and reusability.
    """
    n = len(text)
    m = len(pattern)
    if m > n:
        return []
    if m == 0:
        return list(range(n + 1))

    def compute_hash(s, length):
        """Compute polynomial hash of string s of given length."""
        h_val = 0
        for i in range(length):
            h_val = (h_val * base + ord(s[i])) % mod
        return h_val

    # Precompute h = base^(m-1) % mod
    h_base = pow(base, m - 1, mod)

    pattern_hash = compute_hash(pattern, m)
    window_hash = compute_hash(text, m)

    occurrences = []
    for i in range(n - m + 1):
        if pattern_hash == window_hash:
            # Verify to eliminate false positives
            match = True
            for j in range(m):
                if text[i + j] != pattern[j]:
                    match = False
                    break
            if match:
                occurrences.append(i)

        # Roll hash to next window if not at end
        if i < n - m:
            # Remove leading char, shift, add trailing char
            window_hash = (base * (window_hash - ord(text[i]) * h_base) + ord(text[i + m])) % mod

    return occurrences

One of the most compelling advantages of rabin-karp string search is its natural extension to multiple patterns. The following code searches for a set of patterns of the same length in a single pass by storing pattern hashes in a set for O(1) lookup. For patterns of different lengths, you can group them by length and run the algorithm once per group.

def rabin_karp_multi(text, patterns, base=256, mod=101):
    """
    Rabin-Karp for multiple patterns of equal length.
    Returns dict mapping pattern -> list of positions.
    """
    if not patterns:
        return {}

    m = len(patterns[0])
    n = len(text)
    # Ensure all patterns have same length for this variant
    for p in patterns:
        if len(p) != m:
            raise ValueError("All patterns must have same length in this multi-search variant")

    h = pow(base, m - 1, mod)

    # Hash all patterns and map hash -> patterns (to handle collisions)
    pattern_hash_map = {}
    for p in patterns:
        h_val = 0
        for ch in p:
            h_val = (h_val * base + ord(ch)) % mod
        pattern_hash_map.setdefault(h_val, []).append(p)

    # Hash first window of text
    window_hash = 0
    for i in range(m):
        window_hash = (window_hash * base + ord(text[i])) % mod

    results = {p: [] for p in patterns}
    for i in range(n - m + 1):
        if window_hash in pattern_hash_map:
            # Potential match - verify each pattern with this hash
            for cand in pattern_hash_map[window_hash]:
                if text[i:i+m] == cand:
                    results[cand].append(i)

        if i < n - m:
            window_hash = (window_hash - ord(text[i]) * h) % mod
            window_hash = (window_hash * base + ord(text[i + m])) % mod
            window_hash = (window_hash + mod) % mod

    return results

For performance-critical applications, you can further optimize by using Python's built-in hash or by precomputing prefix hashes to answer any substring hash in O(1). The prefix-hash technique is especially useful for plagiarism detection where you need to compare many substrings.

def rabin_karp_prefix_hash(text, pattern, base=91138233, mod=1000000007):
    """
    Optimized variant using prefix hashes for O(1) substring hash queries.
    Useful when searching for many patterns or repeated queries.
    """
    n = len(text)
    m = len(pattern)
    if m > n:
        return []

    # Precompute prefix hashes and powers
    prefix = [0] * (n + 1)
    power = [1] * (n + 1)
    for i in range(n):
        prefix[i + 1] = (prefix[i] * base + ord(text[i])) % mod
        power[i + 1] = (power[i] * base) % mod

    def get_substring_hash(l, r):
        """Get hash of text[l:r] (r exclusive) in O(1)."""
        return (prefix[r] - prefix[l] * power[r - l]) % mod

    pattern_hash = 0
    for ch in pattern:
        pattern_hash = (pattern_hash * base + ord(ch)) % mod

    matches = []
    for i in range(n - m + 1):
        if get_substring_hash(i, i + m) == pattern_hash:
            if text[i:i+m] == pattern:  # Verify
                matches.append(i)
    return matches

Step-by-Step Example

To make the mechanics of rabin-karp string search concrete, let us walk through a complete example. Suppose we have text T = "ABABAB" and pattern P = "ABA". We will use base b = 256 and a small modulus q = 101 for simplicity, though in practice a larger prime is preferred. The goal is to find all occurrences of "ABA" in "ABABAB".

First, we precompute h = b^(m-1) mod q. Here m = 3, so h = 256^(2) mod 101. Since 256 mod 101 = 54, we compute 54*54 mod 101 = 2916 mod 101 = 88. So h = 88. Next, we compute the hash of the pattern "ABA". Using ord values A=65, B=66, we get: hash(P) = (65*256^2 + 66*256 + 65) mod 101. Stepwise: ((65*256 + 66)*256 + 65) mod 101. Computing incrementally: (65 mod 101 =65), (65*256+66)=16706 mod101=41, (41*256+65)=10561 mod101=57. So hash(P)=57.

Now compute the hash of the first window T[0..2] = "ABA", which is identical to the pattern, so its hash is also 57. Since hashes match, we verify character by character: "ABA" == "ABA" is true, so we record a match at index 0. Next, we roll the hash to window T[1..3] = "BAB". Using the formula: hash_next = ( (57 - 65*88) *256 + 66 ) mod 101. 65*88 mod101 = 5720 mod101=64. 57-64=-7 mod101=94. 94*256+66=24130 mod101=92. So hash("BAB")=92, which does not equal 57, so no verification is needed.

Continuing the Slide

Roll to window T[2..4] = "ABA" again. hash_next = ((92 - 66*88)*256 + 65) mod101. 66*88=5808 mod101=51. 92-51=41. 41*256+65=10561 mod101=57. Hash matches again, verification succeeds, so we record index 2. Roll to final window T[3..5] = "BAB": hash = ((57 -65*88)*256+66) mod101 = 92 again, no match. The algorithm terminates with matches at indices 0 and 2, which is correct.

This example illustrates two critical points. First, the rolling computation is constant time and avoids re-scanning the window. Second, even with a small modulus, the hash correctly filtered out the non-matching window "BAB" without verification. If we had used a poor modulus that caused "BAB" to also hash to 57, we would have performed an unnecessary verification that would have failed, but correctness would be preserved. The table below summarizes the steps.

Complexity Analysis

Analyzing the time and space complexity of rabin-karp string search requires distinguishing between expected and worst-case behavior, because the algorithm's performance depends on hash collisions. In the best and average cases, collisions are rare, and the algorithm runs in linear time. In the worst case, an adversarial input or a poor choice of modulus can force many verifications, degrading performance.

The preprocessing phase computes the initial hashes and the high-order power h, which takes O(m) time and O(1) extra space. The main loop slides over n-m+1 windows, each requiring O(1) time for the rolling hash update. If no hash matches occur, the total time is O(n + m). If a match occurs, verification costs O(m) in the worst case, but this cost is only incurred when hashes collide. With a large random prime modulus, the expected number of spurious hits is O(n/q), which is negligible, yielding expected O(n + m) time.

The worst case occurs when every window's hash equals the pattern's hash, for example when text is "AAAA...A" and pattern is "AAA...A", or when the modulus is 1. Then each of the O(n) windows triggers an O(m) verification, leading to O(n*m) time, identical to the naive algorithm. However, this worst case is extremely unlikely with a properly chosen large prime and is often considered a theoretical concern rather than a practical one for randomized variants.

Complexity Summary Table

Space complexity is a strong point for Rabin-Karp. It uses only a few integer variables for hashes, powers, and indices, resulting in O(1) auxiliary space for single-pattern search. For multi-pattern search, it needs O(k) space to store the hashes of k patterns. This contrasts with algorithms like Aho-Corasick, which require O(total pattern length * alphabet size) for a trie, or KMP which needs O(m) for its prefix table.

When evaluating Big O, remember that the modulus size matters. If q is chosen to be greater than n*m^2, the collision probability becomes very small, and the algorithm can be made to have O(n+m) expected time with high probability. Some textbooks present a Las Vegas variant that always returns the correct answer with expected linear time, and a Monte Carlo variant that skips verification and runs in guaranteed O(n+m) but with a small probability of error.

Variations and Optimizations

Several variations of rabin-karp string search have been developed to address specific limitations or to adapt the algorithm to different problem domains. Understanding these optimizations helps you choose the right variant for your use case and avoid common performance pitfalls.

One classic optimization is using a double hash or two independent moduli. By computing two hashes with different large primes, say q1 = 10^9+7 and q2 = 10^9+9, the collision probability drops to roughly 1/(q1*q2), making it astronomically small. In this variant, a match is declared only when both hashes agree, and many implementations even skip explicit verification because the double collision probability is negligible. This is particularly useful in competitive programming and plagiarism detection where you want to avoid the O(m) verification overhead.

Another important variation handles patterns of different lengths. Instead of grouping patterns by length, you can use the prefix-hash technique shown in the fourth code example. By precomputing prefix hashes and powers for the entire text, you can obtain the hash of any substring in O(1) time, allowing you to check patterns of varying lengths without separate rolling loops. This approach powers many string algorithms and is the foundation for efficient longest common substring and palindrome detection.

Faster Rolling with Bit Operations

For binary alphabets or when speed is paramount, some implementations replace the modulus operation with a natural overflow of 64-bit integers, effectively using modulo 2^64. This exploits the fact that integer overflow in unsigned 64-bit arithmetic is equivalent to modulo 2^64, which is extremely fast on modern CPUs. While this introduces a slightly higher collision probability than a prime modulus, it is often acceptable and eliminates the expensive division operation. This technique is used in the popular Rabin-Karp implementation for the rsync algorithm and in some rolling hash libraries.

For very large texts that do not fit in memory, a streaming or block-based Rabin-Karp can be used. The text is processed in chunks, and the rolling hash state is carried over between blocks. This is essential for searching in files, network streams, or genomic data where n can be gigabytes or more. The algorithm's O(1) memory footprint makes it ideal for such streaming scenarios.

Choosing Base and Modulus Wisely

A common optimization is to choose a random base and modulus at runtime. This randomization protects against adversarial inputs that are crafted to cause many collisions for a fixed modulus. By picking a random large prime from a precomputed list, the algorithm becomes a randomized algorithm with strong expected guarantees even against an adversary who knows the algorithm but not the random choices. In security-sensitive contexts like intrusion detection, this randomization is crucial.

Real-World Applications

Despite being often taught as a theoretical algorithm, rabin-karp string search is widely deployed in practical systems, especially where multi-pattern search or fingerprinting of large data is required. Its ability to compute rolling fingerprints efficiently makes it a building block for many higher-level applications far beyond simple substring search.

One of the most famous applications is plagiarism detection. Systems like MOSS (Measure of Software Similarity) used at Stanford and Turnitin use Rabin-Karp style fingerprinting to detect copied code or text. Documents are broken into k-grams (substrings of length k), each k-gram is hashed, and a subset of hashes (often using winnowing to select representative fingerprints) is compared across documents. The rolling hash allows the system to process millions of documents efficiently. Without rolling hashes, the O(n*m) cost of comparing every k-gram would be prohibitive.

In networking and data deduplication, Rabin-Karp is used for content-defined chunking. Systems like rsync, Dropbox, and backup tools use rolling hashes to split files into variable-length chunks based on hash values. For example, a chunk boundary is declared when the rolling hash modulo some value equals zero. This allows the system to detect duplicate chunks even when files are shifted by insertions or deletions, enabling efficient incremental backups and synchronization. The same principle is used in low-bandwidth file systems like LBFS.

Web, Security, and Bioinformatics

Web servers and databases use Rabin-Karp for multi-pattern matching in other contexts. Intrusion detection systems like Snort need to search network traffic for thousands of attack signatures simultaneously. While Aho-Corasick is often preferred for exact multi-pattern matching, Rabin-Karp is used when signatures are updated frequently because it does not require rebuilding a complex automaton; you simply add a new hash to the set. Similarly, spam filters can use Rabin-Karp to search for many spam keywords in emails in a single pass.

In bioinformatics, the algorithm is used for DNA sequence analysis. Searching for many short patterns (primers, motifs) in a large genome is a classic multi-pattern problem where Rabin-Karp excels. Tools for read mapping and sequence alignment often use rolling hashes to quickly find candidate alignment positions before performing more expensive dynamic programming verification. The alphabet size is small (4 bases), so a small base is used, and the modulus is chosen to be large to handle long sequences.

Comparison with Alternatives

Choosing the right string search algorithm depends on factors like pattern count, alphabet size, text length, and whether preprocessing cost can be amortized. Rabin-Karp is not always the fastest for single-pattern search, but it dominates in specific niches, particularly multi-pattern search and fingerprinting tasks.

The naive algorithm is the simplest baseline: it checks every position character by character. It has O(n*m) worst-case time but requires no preprocessing and is often fast enough for very short patterns or small texts. Knuth-Morris-Pratt (KMP) improves the worst case to O(n+m) by using a prefix function to skip unnecessary comparisons after a mismatch. It guarantees linear time and never re-examines characters, making it excellent for single-pattern search with worst-case guarantees. Boyer-Moore and its variants like Horspool go further by skipping ahead based on the mismatched character, often achieving sublinear time O(n/m) in practice for large alphabets and long patterns, which is why it is used in many text editors and grep implementations.

Aho-Corasick is the classic multi-pattern algorithm that builds a trie with failure links, similar to KMP but for many patterns. It runs in O(n + total pattern length + number of matches) and is optimal for exact multi-pattern search when the pattern set is static. However, building the automaton is more complex and updating the pattern set requires rebuilding. Rabin-Karp, by contrast, has trivial setup for multi-pattern search and is much simpler to implement, though its worst-case time is worse than Aho-Corasick's guarantee.

Feature Comparison Table

In summary, use rabin-karp string search when you need to search for many patterns at once, when you need rolling fingerprints for chunking or similarity detection, or when you want a simple randomized algorithm with good average performance. Use KMP or Boyer-Moore when you need deterministic worst-case guarantees for a single pattern, and use Aho-Corasick when you have a very large, static set of patterns and need optimal worst-case multi-pattern performance.

Common Mistakes and Best Practices

Even though Rabin-Karp is conceptually simple, several subtle implementation errors can lead to incorrect results, poor performance, or integer overflow issues. Being aware of these pitfalls is crucial for writing a correct and efficient implementation.

The most frequent mistake is mishandling negative modulo values during the rolling update. In many languages, the expression (hash - outgoing * h) % mod can be negative, and the language's modulo operator may return a negative result. Failing to normalize this to a positive range causes incorrect hash values for subsequent windows. Always add the modulus before taking modulo again: ((hash - outgoing*h) % mod + mod) % mod, or use Python's pow and ensure you add mod. Another common error is forgetting to precompute h = base^(m-1) mod q correctly, or recomputing it inside the loop, which turns an O(1) update into O(m).

Choosing a bad modulus is another pitfall. Using a small modulus like 101 for large texts guarantees many collisions and destroys performance. Using a non-prime modulus or a modulus that shares factors with the base can create non-uniform hash distributions. Best practice is to use a large random prime, ideally greater than the alphabet size and greater than the expected text length. For Python, 10**9+7, 10**9+9, or 2**61-1 (a Mersenne prime that allows fast modular reduction) are excellent choices. Also, do not use a base that is too small for the alphabet; base should be at least alphabet size to ensure different strings map to different polynomials.

A third mistake is skipping verification after a hash match, assuming collisions never happen. While the probability is low with a good modulus, it is never zero, and skipping verification turns a Las Vegas algorithm into a Monte Carlo algorithm that can return false positives. Always verify character by character when hashes match unless you are using double hashing with a provably negligible error rate and your application tolerates a tiny error probability. Additionally, remember that Rabin-Karp is not ideal for very short patterns where the overhead of hashing outweighs naive comparison, or for binary alphabets with extremely long patterns where Boyer-Moore's skipping is more effective.

Best Practices Checklist

• Use a large prime modulus (e.g., 10^9+7) and a base larger than alphabet size; consider randomizing both at runtime.
• Always normalize modulo results to be non-negative after subtraction.
• Precompute base^(m-1) mod q once outside the loop using fast exponentiation.
• Always verify matches character by character to ensure correctness; consider double hashing if verification is too expensive.
• For multi-pattern search, store pattern hashes in a hash set or dictionary mapping hash to pattern list to handle collisions.
• Profile your use case: for single-pattern search with worst-case guarantees, consider KMP; for many patterns, Rabin-Karp or Aho-Corasick may be better.
• Test with edge cases: empty pattern, pattern longer than text, text with repeated characters, and adversarial collision cases.

Interview Questions

Rabin-Karp is a favorite topic in coding interviews because it tests understanding of hashing, modular arithmetic, and algorithmic trade-offs. Below are common questions with guidance on how to approach them.

1. How does Rabin-Karp handle hash collisions, and why is verification necessary?

Answer: A collision occurs when two different strings have the same hash value modulo q. Rabin-Karp handles this by verifying every hash match with a direct character-by-character comparison. Verification is necessary because hashing is lossy modulo a small prime; without it, the algorithm could report false positives. The expected number of collisions is low with a large prime, so verification rarely happens, preserving average linear time while guaranteeing correctness. An advanced follow-up is to discuss double hashing to reduce collision probability so much that verification can be skipped with high confidence.

2. Implement Rabin-Karp to find all occurrences of a pattern, and analyze its complexity.

Answer: Candidates should write code similar to the robust implementation above, explaining the rolling hash formula, precomputation of h, and the loop that slides the window. They should state preprocessing O(m), search O(n+m) average and O(n*m) worst case, and O(1) extra space. Interviewers often look for correct modulo handling and the verification step. A strong answer also mentions the choice of base and modulus and why a large prime is used.

3. How would you extend Rabin-Karp to search for multiple patterns efficiently?

Answer: Compute the hash for each pattern and store them in a hash set or dictionary. Then slide a window over the text, computing the rolling hash once per position and checking if it exists in the set. If patterns have different lengths, group them by length and run the algorithm per group, or use prefix hashes to get any substring hash in O(1). This achieves O(n + k*m) average time for k patterns of length m, versus O(k*n*m) for naive repeated search. Mention the trade-off versus Aho-Corasick, which has better worst-case guarantees but higher implementation complexity.

4. When would you prefer Rabin-Karp over KMP or Boyer-Moore?

Answer: Prefer Rabin-Karp when searching for many patterns simultaneously, when you need rolling fingerprints for applications like plagiarism detection or chunking, or when simplicity and average-case linear time are more important than worst-case guarantees. Prefer KMP when you need deterministic O(n+m) worst-case time for a single pattern, and Boyer-Moore when patterns are long and the alphabet is large, allowing large skips. Rabin-Karp's strength is multi-pattern and fingerprinting; its weakness is worst-case O(n*m) due to collisions.

5. What is the effect of choosing a small modulus, and how would you choose base and modulus in practice?

Answer: A small modulus increases collision probability, leading to many spurious hits and frequent O(m) verifications, degrading performance toward O(n*m). In practice, choose a large prime modulus like 10^9+7 or 10^9+9, or a 61-bit Mersenne prime for fast reduction, and a base at least as large as the alphabet size, often 256 for bytes or a random odd number greater than alphabet size. Randomizing the modulus at runtime provides protection against adversarial inputs. For very low error tolerance, use two independent moduli.