Rabin Karp String Matching in DSA C# - Build from Scratch

Rabin Karp String Matching

📖 Scenario: You are building a simple text search tool that finds a small pattern inside a larger text efficiently. This is useful in many real-world cases like searching for a word in a document or detecting plagiarism.

🎯 Goal: Build a program that uses the Rabin Karp algorithm to find all starting positions of a given pattern inside a text string.

📋 What You'll Learn

Create a string variable text with the exact value "abracadabra".

Create a string variable pattern with the exact value "abra".

Create an integer variable prime with the exact value 101 to use as the modulus in hashing.

Implement the Rabin Karp algorithm using a rolling hash technique with variables textHash, patternHash, and h.

Print the starting indices of all matches found in the format Match found at index: X.

💡 Why This Matters

🌍 Real World

Text search is used in editors, search engines, and plagiarism detection tools to quickly find patterns in large documents.

💼 Career

Understanding Rabin Karp helps in roles involving text processing, software development, and algorithm optimization.

1

Create the text and pattern strings

Create a string variable called text with the value "abracadabra" and a string variable called pattern with the value "abra".

DSA C#

# Create the text and pattern strings
# Your code here

Hint

Use string type and assign the exact values given.

2

Set the prime modulus for hashing

Create an integer variable called prime and set it to 101 to use as the modulus in the hashing process.

DSA C#

string text = "abracadabra";
string pattern = "abra";
# Create the prime modulus variable
# Your code here

Hint

This prime number helps reduce hash collisions in the Rabin Karp algorithm.

3

Implement the Rabin Karp rolling hash setup

Create integer variables textHash, patternHash, and h all initialized to 0. Then write a for loop with variable i from 0 to pattern.Length - 1 to calculate the initial hash values and the value of h for rolling the hash.

DSA C#

string text = "abracadabra";
string pattern = "abra";
int prime = 101;
// Initialize hash variables
// Your code here

Hint

Calculate h as 256^(pattern length - 1) mod prime. Then calculate initial hashes for pattern and first text window.

4

Find and print all pattern matches in the text

Write a for loop with variable i from 0 to text.Length - pattern.Length. Inside, check if patternHash equals textHash. If yes, verify character by character with a nested for loop using variable j. If all characters match, print Match found at index: i. Then update textHash for the next window using the rolling hash formula.

DSA C#

string text = "abracadabra";
string pattern = "abra";
int prime = 101;

int textHash = 0;
int patternHash = 0;
int h = 1;

for (int i = 0; i < pattern.Length - 1; i++)
{
    h = (h * 256) % prime;
}

for (int i = 0; i < pattern.Length; i++)
{
    patternHash = (256 * patternHash + pattern[i]) % prime;
    textHash = (256 * textHash + text[i]) % prime;
}

// Find matches and print indices
// Your code here

Hint

Use a rolling hash to update textHash for the next substring. Print matches exactly as shown.

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