Rabin Karp String Matching in DSA C

Mental Model

We use a number (hash) to represent a string part and compare these numbers to find matches quickly.

Analogy: Imagine checking if a small book page is inside a big book by comparing page numbers instead of reading every word each time.

Text:  T  h  i  s  i  s  a  t  e  s  t  
Index: 0->1->2->3->4->5->6->7->8->9->10->11->null
Pattern: t  e  s  t
Index: 0->1->2->3->null

Dry Run Walkthrough

Input: text: "testtext", pattern: "test"

Goal: Find all starting positions in text where pattern "test" appears.

Step 1: Calculate hash of pattern "test" and first 4 characters of text "test"

pattern_hash=hash("test")=X, text_hash=hash("test")=X

Why: We need these hashes to compare quickly without checking characters one by one.

Step 2: Compare pattern_hash and text_hash at index 0

pattern_hash == text_hash, check characters: 't'=='t', 'e'=='e', 's'=='s', 't'=='t'

Why: Hashes match, so verify characters to confirm actual match.

Step 3: Slide window by 1: remove 't', add 'e' to text_hash for substring "estt"

text_hash=hash("estt") != pattern_hash

Why: Update hash efficiently to check next substring without full recomputation.

Step 4: Slide window by 1: remove 'e', add 's' to text_hash for substring "stte"

text_hash != pattern_hash

Why: Continue sliding to check all substrings.

Step 5: Slide window by 1: remove 's', add 't' to text_hash for substring "ttex"

text_hash != pattern_hash

Why: Keep sliding until end of text.

Step 6: Slide window by 1: remove 't', add 'x' to text_hash for substring "text"

text_hash != pattern_hash

Why: Checked all possible positions, only match at index 0.

Result:

Matches found at indices: 0 -> null

Annotated Code

DSA C

#include <stdio.h>
#include <string.h>
#define d 256
#define q 101

void rabinKarp(char* text, char* pattern) {
    int n = strlen(text);
    int m = strlen(pattern);
    int i, j;
    int p = 0; // hash value for pattern
    int t = 0; // hash value for text
    int h = 1;

    // The value of h would be "pow(d, m-1)%q"
    for (i = 0; i < m - 1; i++)
        h = (h * d) % q;

    // Calculate the hash value of pattern and first window of text
    for (i = 0; i < m; i++) {
        p = (d * p + pattern[i]) % q;
        t = (d * t + text[i]) % q;
    }

    // Slide the pattern over text one by one
    for (i = 0; i <= n - m; i++) {
        // Check the hash values of current window of text and pattern
        if (p == t) {
            // If the hash values match, check characters one by one
            for (j = 0; j < m; j++) {
                if (text[i + j] != pattern[j])
                    break;
            }
            if (j == m)
                printf("Pattern found at index %d\n", i);
        }

        // Calculate hash value for next window of text
        if (i < n - m) {
            t = (d * (t - text[i] * h) + text[i + m]) % q;
            // We might get negative value of t, convert it to positive
            if (t < 0)
                t = t + q;
        }
    }
}

int main() {
    char text[] = "testtext";
    char pattern[] = "test";
    rabinKarp(text, pattern);
    return 0;
}

for (i = 0; i < m - 1; i++) h = (h * d) % q;

Calculate h = d^(m-1) mod q for rolling hash

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

Compute initial hash values for pattern and first text window

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 hashes match, verify characters to confirm pattern

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

Update text hash for next window using rolling hash formula

Output

Pattern found at index 0

Complexity Analysis

Time: O(n + m) because we compute hashes once and slide over text once, verifying matches only when hashes match

Space: O(1) because we use fixed extra space for hash calculations and counters

vs Alternative: Compared to naive O(n*m) approach that checks every substring fully, Rabin-Karp uses hashing to skip unnecessary checks, improving average performance

Edge Cases

Empty pattern

Pattern matches at every index 0 to n (n+1 matches printed)

DSA C

int m = strlen(pattern); when m==0, hash loops skipped but main loop runs i=0 to n and verification passes (j==m==0)

Pattern longer than text

No matches found, loop does not run

DSA C

for (i = 0; i <= n - m; i++) (loop condition prevents invalid access)

Pattern equals text

Single match found at index 0

DSA C

if (p == t) { ... } (hash comparison and verification)

When to Use This Pattern

When you need to find a substring quickly multiple times and want to avoid checking every character repeatedly, use Rabin-Karp because it uses hashing to speed up comparisons.

Common Mistakes

Mistake: Not handling negative hash values after rolling hash update
Fix: Add check to convert negative hash to positive by adding modulus q

Mistake: Comparing hashes only without verifying characters
Fix: Always verify characters when hashes match to avoid false positives

Summary

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

Use when you want faster substring search than naive checking, especially for multiple searches.

The key is using a rolling hash to update substring hashes efficiently instead of recomputing from scratch.

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