Rabin Karp String Matching in DSA C# - Execution Trace

Concept Flow - Rabin Karp String Matching

Start

↓

Compute pattern hash

↓

Compute initial window hash in text

↓

For each window in text

↓

Compare hashes

↓

Hashes equal?

↓

Check actual substring

↓

Match?

↓

Report match index

↓

Slide window

↓

Update rolling hash

↓

Repeat

↓

Slide window

↓

Update rolling hash

↓

End

The algorithm computes a hash for the pattern and for each text window, compares hashes, and if equal, confirms by substring check, then slides the window and updates the hash.

Execution Sample

DSA C#

pattern = "abc"
text = "abdabcbabc"
Compute hash of pattern
Slide over text windows
Compare hashes
Confirm matches
Report indices

This code finds all occurrences of "abc" in the text "abdabcbabc" using Rabin Karp hashing.

Execution Table

Step	Operation	Window Start Index	Pattern Hash	Current Window Hash	Hashes Equal?	Substring Check	Match Found	Visual State
1	Compute pattern hash	-	294	-	-	-	-	-
2	Compute initial window hash	0	294	293	No	-	No	"abd"
3	Slide window	1	294	294	Yes	Check substring "bda"	No	"bda"
4	Slide window	2	294	294	Yes	Check substring "dab"	No	"dab"
5	Slide window	3	294	294	Yes	Check substring "abc"	Yes	"abc"
6	Report match	3	294	294	Yes	Confirmed	Yes	"abc" at index 3
7	Slide window	4	294	295	No	-	No	"bcb"
8	Slide window	5	294	294	Yes	Check substring "cba"	No	"cba"
9	Slide window	6	294	294	Yes	Check substring "bab"	No	"bab"
10	Slide window	7	294	294	Yes	Check substring "abc"	Yes	"abc"
11	Report match	7	294	294	Yes	Confirmed	Yes	"abc" at index 7
12	End of text reached	-	-	-	-	-	-	-

💡 Reached end of text windows; no more substrings to check.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	After Step 9	After Step 10	Final
pattern_hash	-	294	294	294	294	294	294	294	294	294	294
current_window_hash	-	293	294	294	294	294	295	294	294	294	-
window_start_index	-	0	1	2	3	3	4	5	6	7	-
match_found	-	No	No	No	Yes	Yes	No	No	No	Yes	-

Key Moments - 3 Insights

Why do we check the actual substring even when hashes are equal?

Because different strings can have the same hash (hash collision). The substring check confirms the match. See steps 3,4,5,8,9,10 in execution_table where hashes equal but substring check decides match.

How is the rolling hash updated when sliding the window?

The hash removes the leftmost character's contribution and adds the new rightmost character's value, keeping computation efficient. This is shown in the 'Slide window' operations updating current_window_hash in execution_table.

Why does the algorithm stop at step 12?

Because the window has reached the end of the text and no further substrings of pattern length remain to check, as noted in exit_note.

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what is the substring checked?

A "bda"

B "dab"

C "abc"

D "abd"

💡 Hint

Refer to the 'Substring Check' column at step 5 in execution_table.

At which step does the first match get reported?

A Step 5

B Step 6

C Step 4

D Step 7

💡 Hint

Look at the 'Match Found' and 'Operation' columns in execution_table to find when a match is reported.

If the pattern hash was different, how would the 'Hashes Equal?' column change?

A Fewer or no 'Yes' entries

B No change

C More 'Yes' entries

D All 'Yes'

💡 Hint

Check how 'Hashes Equal?' depends on pattern_hash and current_window_hash in execution_table.

Concept Snapshot

Rabin Karp String Matching:
- Compute hash of pattern and initial text window
- Slide window over text, update hash efficiently
- If hashes match, check substring to confirm
- Report all matching indices
- Efficient for multiple pattern searches
- Handles collisions by substring verification

Full Transcript

Rabin Karp String Matching works by first computing a hash value for the pattern. Then it computes the hash for the first window of text with the same length as the pattern. It slides this window one character at a time over the text, updating the hash efficiently by removing the leftmost character and adding the new rightmost character. At each step, it compares the current window hash with the pattern hash. If they are equal, it checks the actual substring to confirm a match because different strings can have the same hash. When a match is confirmed, it reports the starting index. The process continues until the window reaches the end of the text. This method is efficient and useful for finding all occurrences of a pattern in a 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