Rabin Karp String Matching in DSA C#

Mental Model

We use a number to represent a string so we can quickly check if two strings might be the same before checking each character.

Analogy: Imagine you want to find a word in a book. Instead of reading every word, you first check the page number and line number where the word might be, then look closely only if those numbers match.

Text:  T h i s   i s   a   t e x t
Pattern:     t e x t
Hash: [hash of 'text'] -> compare with text hash

Dry Run Walkthrough

Input: text: 'ababcabc', pattern: 'abc'

Goal: Find all positions where 'abc' appears in 'ababcabc' using Rabin Karp

Step 1: Calculate hash of pattern 'abc' and first substring 'aba' of text

pattern hash = h('abc')
current text window = 'aba', hash = h('aba')

Why: We need to compare hashes to quickly find possible matches

Step 2: Compare pattern hash with current text window hash; no match

pattern hash != h('aba')

Why: Hashes differ, so 'aba' is not the pattern

Step 3: Slide window by one: new substring 'bab', update hash using rolling hash

current text window = 'bab', hash = h('bab')

Why: Efficiently update hash without recalculating from scratch

Step 4: Compare pattern hash with 'bab' hash; no match

pattern hash != h('bab')

Why: Hashes differ, so 'bab' is not the pattern

Step 5: Slide window by one: new substring 'abc', update hash

current text window = 'abc', hash = h('abc')

Why: Check next substring for possible match

Step 6: Hashes match; verify characters one by one; match confirmed at index 2

pattern hash == h('abc')
verified characters match

Why: Hash collision possible, so verify actual characters

Step 7: Slide window by one: new substring 'bca', update hash

current text window = 'bca', hash = h('bca')

Why: Continue searching for other matches

Step 8: Hashes differ; no match

pattern hash != h('bca')

Why: No match here

Step 9: Slide window by one: new substring 'cab', update hash

current text window = 'cab', hash = h('cab')

Why: Continue searching

Step 10: Hashes differ; no match

pattern hash != h('cab')

Why: No match here

Step 11: Slide window by one: new substring 'abc', update hash

current text window = 'abc', hash = h('abc')

Why: Check last possible substring

Step 12: Hashes match; verify characters; match confirmed at index 5

pattern hash == h('abc')
verified characters match

Why: Found second match

Result:

Matches found at indices: 2, 5

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

class RabinKarp
{
    private const int Base = 256; // number of characters in input alphabet
    private const int Prime = 101; // a prime number for modulo

    public static List<int> Search(string text, string pattern)
    {
        int n = text.Length;
        int m = pattern.Length;
        List<int> result = new List<int>();

        if (m > n || m == 0) return result; // edge case: pattern longer than text or empty

        int patternHash = 0; // hash value for pattern
        int windowHash = 0;  // hash value for current window in text
        int h = 1; // the value of Base^(m-1) used to remove leading digit

        // Calculate h = pow(Base, m-1) % Prime
        for (int i = 0; i < m - 1; i++)
            h = (h * Base) % Prime;

        // Calculate initial hash values for pattern and first window
        for (int i = 0; i < m; i++)
        {
            patternHash = (Base * patternHash + pattern[i]) % Prime;
            windowHash = (Base * windowHash + text[i]) % Prime;
        }

        // Slide the pattern over text one by one
        for (int i = 0; i <= n - m; i++)
        {
            // Check hash values of current window and pattern
            if (patternHash == windowHash)
            {
                // If hash matches, check characters one by one
                int j;
                for (j = 0; j < m; j++)
                {
                    if (text[i + j] != pattern[j])
                        break;
                }

                if (j == m)
                    result.Add(i); // match found at index i
            }

            // Calculate hash for next window
            if (i < n - m)
            {
                windowHash = (Base * (windowHash - text[i] * h) + text[i + m]) % Prime;

                // We might get negative value, convert it to positive
                if (windowHash < 0)
                    windowHash += Prime;
            }
        }

        return result;
    }

    static void Main()
    {
        string text = "ababcabc";
        string pattern = "abc";
        var matches = Search(text, pattern);
        Console.WriteLine("Matches found at indices: " + string.Join(", ", matches));
    }
}

for (int i = 0; i < m - 1; i++) h = (h * Base) % Prime;

Calculate multiplier for leading character removal in rolling hash

for (int i = 0; i < m; i++) { patternHash = (Base * patternHash + pattern[i]) % Prime; windowHash = (Base * windowHash + text[i]) % Prime; }

Compute initial hash values for pattern and first text window

for (int i = 0; i <= n - m; i++)

Slide window over text from start to end

if (patternHash == windowHash)

Check if current window hash matches pattern hash

for (j = 0; j < m; j++) if (text[i + j] != pattern[j]) break;

Verify characters one by one to confirm match

if (j == m) result.Add(i);

Add index to result if full match found

windowHash = (Base * (windowHash - text[i] * h) + text[i + m]) % Prime;

Update hash for next window using rolling hash formula

if (windowHash < 0) windowHash += Prime;

Ensure hash value stays positive

Output

Matches found at indices: 2, 5

Complexity Analysis

Time: O(n + m) because we compute initial hashes in O(m) and slide over text in O(n), with rare character checks on hash matches

Space: O(k) where k is number of matches stored, otherwise O(1) for variables

vs Alternative: Compared to naive O(n*m) checking each substring fully, Rabin Karp uses hashing to skip many checks, improving average time

Edge Cases

Empty pattern string

Returns empty list immediately, no matches

DSA C#

if (m > n || m == 0) return result;

Pattern longer than text

Returns empty list immediately, no matches

DSA C#

if (m > n || m == 0) return result;

Pattern equals text

Returns index 0 as match

DSA C#

for (int i = 0; i <= n - m; i++)

When to Use This Pattern

When you need to find a pattern in a text efficiently and want to avoid checking every character repeatedly, use Rabin Karp because it uses hashing to quickly skip non-matching parts.

Common Mistakes

Mistake: Not handling negative hash values after rolling hash update
Fix: Add code to add prime number to hash if it becomes negative

Mistake: Not verifying characters after hash match, causing false positives
Fix: Always check characters one by one when hashes match

Mistake: Calculating rolling hash from scratch each time instead of updating
Fix: Use rolling hash formula to update hash efficiently

Summary

Finds all occurrences of a pattern in a text using hashing to speed up matching.

Use when you want faster pattern search than checking every substring fully.

The key is to represent strings as numbers and update these numbers quickly as you slide through the text.

Practice

1. What is the main idea behind the Rabin Karp String Matching algorithm?

easy

A. Sort the text and pattern before matching

B. Compare each character of pattern with text directly

C. Use hashing to find pattern matches efficiently

D. Use recursion to find all pattern occurrences

Solution

1. Step 1: Understand Rabin Karp approach

   Rabin Karp uses hashing to convert strings into numbers for quick comparison.

2. Step 2: Compare hash values instead of characters

   It compares hash of pattern with hash of text substrings to find matches efficiently.

3. Final Answer:

   Use hashing to find pattern matches efficiently -> Option C

4. Quick Check:

   Hashing = Efficient matching [OK]

Hint: Remember Rabin Karp uses hashing for fast pattern search [OK]

Common Mistakes:

• Thinking it compares characters one by one always
• Confusing with brute force matching
• Assuming sorting is involved

2. Which of the following is the correct way to calculate the initial hash for a substring in Rabin Karp (assuming base = 256 and prime = 101)?

easy

A. hash = (hash - char) % prime

B. hash = (hash + base * char) % prime

C. hash = (char * base) % prime

D. hash = (hash * base + char) % prime

Solution

1. Step 1: Understand rolling hash formula

   The rolling hash updates as hash = (hash * base + new_char) % prime.

2. Step 2: Apply formula for initial hash

   Initial hash is calculated by iterating characters and applying this formula cumulatively.

3. Final Answer:

   hash = (hash * base + char) % prime -> Option D

4. Quick Check:

   Rolling hash formula = hash = (hash * base + char) % prime [OK]

Hint: Use (hash * base + char) % prime for rolling hash [OK]

Common Mistakes:

• Adding instead of multiplying by base
• Subtracting characters incorrectly
• Ignoring modulo operation

3. What will be the output of the following C# code snippet using Rabin Karp to find pattern "abc" in text "ababc"?

string text = "ababc";
string pattern = "abc";
List<int> matches = RabinKarpSearch(text, pattern);
Console.WriteLine(string.Join(",", matches));

List<int> RabinKarpSearch(string txt, string pat) {
    int baseVal = 256, prime = 101;
    int m = pat.Length, n = txt.Length;
    int patHash = 0, txtHash = 0, h = 1;
    List<int> result = new List<int>();

    for (int i = 0; i < m - 1; i++) h = (h * baseVal) % prime;

    for (int i = 0; i < m; i++) {
        patHash = (baseVal * patHash + pat[i]) % prime;
        txtHash = (baseVal * txtHash + txt[i]) % prime;
    }

    for (int i = 0; i <= n - m; i++) {
        if (patHash == txtHash) {
            bool match = true;
            for (int j = 0; j < m; j++) {
                if (txt[i + j] != pat[j]) {
                    match = false;
                    break;
                }
            }
            if (match) result.Add(i);
        }
        if (i < n - m) {
            txtHash = (baseVal * (txtHash - txt[i] * h) + txt[i + m]) % prime;
            if (txtHash < 0) txtHash += prime;
        }
    }
    return result;
}

medium

A. 1,2

B. 2

C. 0,2

D. No matches

Solution

1. Step 1: Identify pattern occurrences in text

   Pattern "abc" appears starting at index 2 in "ababc". Also, substring at index 0 is "aba" which is not a match.

2. Step 2: Check hash and character matches

   Hashes match only at index 2 (initial hashes differ at index 0 and 1), and character check passes at index 2. So only index 2 is added.

3. Final Answer:

   2 -> Option B

4. Quick Check:

   Pattern found at index 2 [OK]

Hint: Check both hash and characters to confirm matches [OK]

Common Mistakes:

• Assuming all hash matches are valid
• Ignoring character verification after hash match
• Miscounting indices starting from 1

4. Identify the bug in this Rabin Karp substring search code snippet:

int baseVal = 256, prime = 101;
int m = pattern.Length, n = text.Length;
int patHash = 0, txtHash = 0, h = 1;
for (int i = 0; i <= m - 1; i++) h = (h * baseVal) % prime;
for (int i = 0; i < m; i++) {
    patHash = (baseVal * patHash + pattern[i]) % prime;
    txtHash = (baseVal * txtHash + text[i]) % prime;
}
// rest of code omitted

medium

A. Loop for h calculation should run till m-2, not m-1

B. Modulo prime missing in hash calculations

C. Using <= in loop causes out of range error

D. Base value should be 128, not 256

Solution

1. Step 1: Analyze h calculation loop

   h is used as base^(m-1) % prime, so loop should run m-1 times, i.e., i from 0 to m-2.

2. Step 2: Identify off-by-one error

   Loop runs from i=0 to i=m-1 (inclusive), which is m times, causing incorrect h value.

3. Final Answer:

   Loop for h calculation should run till m-2, not m-1 -> Option A

4. Quick Check:

   h loop runs m-1 times [OK]

Hint: Calculate h with loop running m-1 times only [OK]

Common Mistakes:

• Using <= instead of < in loop
• Forgetting modulo in hash updates
• Wrong base value choice

5. You want to find all occurrences of pattern "test" in a very large text using Rabin Karp. Which optimization helps reduce false positives caused by hash collisions?

hard

A. Use a larger prime number for modulo operations

B. Skip character comparison after hash match

C. Use base value as 1 to simplify hash

D. Only check first character after hash match

Solution

1. Step 1: Understand hash collisions in Rabin Karp

   Hash collisions occur when different substrings produce same hash value, causing false positives.

2. Step 2: Use larger prime to reduce collisions

   A larger prime number reduces chances of collisions by spreading hash values more evenly.

3. Final Answer:

   Use a larger prime number for modulo operations -> Option A

4. Quick Check:

   Larger prime = fewer collisions [OK]

Hint: Choose bigger prime to minimize hash collisions [OK]

Common Mistakes:

• Skipping character checks after hash match
• Using base 1 which weakens hash uniqueness
• Checking only first character after hash match