Rabin Karp String Matching in DSA C - Execution Trace

Concept Flow - Rabin Karp String Matching

Start

↓

Calculate pattern hash

↓

Calculate initial text window hash

↓

For each window in text

↓

Compare pattern hash and window hash

Yes No↓

Check chars

↓

Match?

↓

Report

↓

End

The algorithm calculates hash of the pattern and text windows, compares hashes, and if equal, checks characters to find matches.

Execution Sample

DSA C

pattern = "abc";
text = "abdabcbabc";
for each window in text:
  if hash(window) == hash(pattern):
    check characters
  slide window and update hash

This code slides a window over the text, compares hash values with the pattern hash, and confirms matches by character check.

Execution Table

Step	Operation	Window Start Index	Pattern Hash	Window Hash	Hash Match?	Character Check	Match Found	Visual State
1	Calculate pattern hash	-	294	-	-	-	-	-
2	Calculate initial window hash (text[0..2])	0	294	294	Yes	Compare 'abc' with 'abd'	No	"a b d" -> ...
3	Slide window to text[1..3]	1	294	303	No	-	No	"b d a" -> ...
4	Slide window to text[2..4]	2	294	294	Yes	Compare 'abc' with 'dab'	No	"d a b" -> ...
5	Slide window to text[3..5]	3	294	294	Yes	Compare 'abc' with 'abc'	Yes	"a b c" -> ...
6	Slide window to text[4..6]	4	294	303	No	-	No	"b c b" -> ...
7	Slide window to text[5..7]	5	294	294	Yes	Compare 'abc' with 'cba'	No	"c b a" -> ...
8	Slide window to text[6..8]	6	294	294	Yes	Compare 'abc' with 'bab'	No	"b a b" -> ...
9	Slide window to text[7..9]	7	294	294	Yes	Compare 'abc' with 'abc'	Yes	"a b c" -> ...
10	Slide window to text[8..10]	-	294	-	-	-	-	-
11	End of text reached	-	294	-	-	-	-	-

💡 Reached end of text windows; no more windows 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
window_start_index	-	0	1	2	3	4	5	6	7	-	-
window_hash	-	294	303	294	294	303	294	294	294	-	-
match_found	-	No	No	No	Yes	No	No	No	Yes	-	-

Key Moments - 3 Insights

Why do we check characters even if the hashes match?

Because different strings can have the same hash (hash collision). The character check confirms the match, as shown in steps 2, 4, and 5 in the execution_table.

How is the window hash updated when sliding the window?

The hash is updated by removing the leftmost character's contribution and adding the new rightmost character's contribution, avoiding full recomputation. This is why window_hash changes between steps, e.g., step 3.

Why does the algorithm stop after the last window?

Because the window cannot slide beyond the text length minus pattern length. Step 11 shows the end of text windows reached.

Visual Quiz - 3 Questions

Look at the execution_table at step 5. What is the window start index and was a match found?

A Start index 3, match found Yes

B Start index 3, match found No

C Start index 2, match found Yes

D Start index 4, match found Yes

💡 Hint

Check the 'Window Start Index' and 'Match Found' columns in row for step 5.

At which step does the window hash first differ from the pattern hash?

A Step 2

B Step 3

C Step 4

D Step 5

💡 Hint

Look at the 'Window Hash' and 'Pattern Hash' columns in the execution_table rows.

If the pattern was "abd" instead of "abc", how would the match found at step 2 change?

A Match found would be Yes

B Match found would be No

C Window hash would not be calculated

D Algorithm would stop early

💡 Hint

Consider that the pattern hash would change and compare with window hash at step 2.

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 characters to confirm
- Handles collisions by verification
- Stops when window reaches text end

Full Transcript

Rabin Karp string matching works by calculating a hash value for the pattern and for each window of text of the same length. It slides the window one character at a time, updating the hash efficiently without recomputing from scratch. When the hash of the current window matches the pattern hash, it checks the characters one by one to confirm a real match, because different strings can have the same hash. The process continues until the window reaches the end of the text. This method speeds up searching by avoiding unnecessary character comparisons when hashes differ.

Practice

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

easy

A. Compare each character one by one without hashing

B. Use hashing to find pattern matches efficiently

C. Sort the text and pattern before matching

D. Use recursion to find all pattern occurrences

Solution

1. Step 1: Understand the algorithm's 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 values of the pattern and text substrings to find matches efficiently.

3. Final Answer:

   Use hashing to find pattern matches efficiently -> Option B

4. Quick Check:

   Hashing = Efficient matching [OK]

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

Common Mistakes:

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

2. Which of the following is the correct way to update the rolling hash in Rabin Karp when moving from substring s[i..i+m-1] to s[i+1..i+m]?

easy

A. hash = (hash * base) + s[i] - s[i+m]

B. hash = (hash + s[i] * power) * base - s[i+m]

C. hash = (hash - s[i] * power) * base + s[i+m]

D. hash = (hash - s[i+m] * power) + s[i]

Solution

1. Step 1: Understand rolling hash update formula

   Remove the leftmost character's weighted value, multiply by base, add new character.

2. Step 2: Apply formula to substring shift

   hash = (hash - s[i] * power) * base + s[i+m] correctly updates the hash.

3. Final Answer:

   hash = (hash - s[i] * power) * base + s[i+m] -> Option C

4. Quick Check:

   Remove left char, multiply, add right char [OK]

Hint: Subtract old char, multiply hash, add new char [OK]

Common Mistakes:

• Adding instead of subtracting old char
• Wrong order of operations
• Mixing indices of characters

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

#include 
#include 
#define base 256
#define prime 101

int main() {
    char text[] = "ababc";
    char pattern[] = "abc";
    int n = strlen(text), m = strlen(pattern);
    int p = 0, t = 0, h = 1, i, j;

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

    for (i = 0; i < m; i++) {
        p = (base * p + pattern[i]) % prime;
        t = (base * t + text[i]) % prime;
    }

    for (i = 0; i <= n - m; i++) {
        if (p == t) {
            for (j = 0; j < m; j++) {
                if (text[i+j] != pattern[j])
                    break;
            }
            if (j == m)
                printf("Pattern found at index %d\n", i);
        }
        if (i < n - m) {
            t = (base * (t - text[i] * h) + text[i + m]) % prime;
            if (t < 0) t = t + prime;
        }
    }
    return 0;
}

medium

A. Pattern found at index 2

B. Pattern found at index 0

C. Pattern found at index 1

D. No pattern found

Solution

1. Step 1: Calculate initial hashes and check first substring

   Pattern "abc" hash matches substring "aba" at index 0? No, characters differ.

2. Step 2: Slide window and check next substring

   At index 1, substring "bab" hash differs. At index 2, substring "abc" matches pattern exactly.

3. Final Answer:

   Pattern found at index 2 -> Option A

4. Quick Check:

   Match at index 2 = Pattern found at index 2 [OK]

Hint: Check hash then verify substring match [OK]

Common Mistakes:

• Assuming match at index 0 without verification
• Ignoring negative hash correction
• Not verifying characters after hash match

4. Identify the bug in this Rabin Karp hash update snippet:

t = (base * (t - text[i] * h) + text[i + m]) % prime;
if (t < 0) t = t - prime;

medium

A. Should add prime instead of subtracting when t < 0

B. Multiplication order is wrong

C. Index i + m is out of range

D. No bug, code is correct

Solution

1. Step 1: Understand negative hash correction

   If hash becomes negative after modulo, add prime to keep it positive.

2. Step 2: Check given code's correction

   Code subtracts prime when t < 0, which makes t more negative. It should add prime.

3. Final Answer:

   Should add prime instead of subtracting when t < 0 -> Option A

4. Quick Check:

   Negative hash fix = add prime [OK]

Hint: Add prime if hash is negative after modulo [OK]

Common Mistakes:

• Subtracting prime instead of adding
• Ignoring negative hash values
• Confusing modulo operation behavior

5. You want to find all occurrences of pattern "aaa" in text "aaaaaa" using Rabin Karp. How many matches will the algorithm report and why?

hard

A. 0 matches, because pattern length equals text length

B. 3 matches, because only non-overlapping occurrences count

C. 1 match, because repeated characters cause hash collision

D. 4 matches, because overlapping occurrences are counted

Solution

1. Step 1: Count possible substrings of length 3 in text

   Text length 6, pattern length 3, so 6 - 3 + 1 = 4 substrings.

2. Step 2: Check each substring for pattern match

   All substrings "aaa" at indices 0,1,2,3 match pattern including overlaps.

3. Final Answer:

   4 matches, because overlapping occurrences are counted -> Option D

4. Quick Check:

   Overlapping matches counted = 4 [OK]

Hint: Count all substrings including overlaps [OK]

Common Mistakes:

• Ignoring overlapping matches
• Assuming only non-overlapping matches count
• Confusing hash collisions with matches