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 if a small word (pattern) exists inside a larger text. This is like searching for a word in a book.

🎯 Goal: Build a program that uses the Rabin Karp algorithm to find if a pattern string exists in a given text string by comparing hash values.

📋 What You'll Learn

Create variables for the text and pattern strings

Set up variables for the pattern length, text length, and hash values

Implement the Rabin Karp rolling hash logic to check for pattern matches

Print the starting index of the pattern in the text if found, or -1 if not found

💡 Why This Matters

🌍 Real World

Text search is used in search engines, text editors, and DNA sequence analysis.

💼 Career

Understanding string matching algorithms like Rabin Karp is important for software development roles involving text processing and search optimization.

1

Create the text and pattern strings

Create a char array called text with the value "hello world" and a char array called pattern with the value "world".

DSA C

# Your code here

Hint

Use double quotes for strings and square brackets for arrays.

2

Set up lengths and initial hash variables

Create int variables m and n to store the lengths of pattern and text respectively using strlen. Also create int variables pattern_hash, text_hash, and h and initialize them to 0, 0, and 1 respectively.

DSA C

char text[] = "hello world";
char pattern[] = "world";
# Your code here

Hint

Use strlen from string.h to get string lengths.

3

Calculate initial hash values and rolling hash logic

Use a for loop with variable i from 0 to m - 1 to calculate the initial hash values for pattern_hash and text_hash. Also calculate h as (h * 256) % 101 inside a loop from 0 to m - 2. Then use a for loop with variable i from 0 to n - m to slide over the text, compare hash values, and check character by character for a match. If found, print the index i and return. If no match is found after the loop, print -1.

DSA C

char text[] = "hello world";
char pattern[] = "world";

int m = strlen(pattern);
int n = strlen(text);

int pattern_hash = 0;
int text_hash = 0;
int h = 1;

// Your code here

Hint

Use the Rabin Karp rolling hash formula and compare characters only if hashes match.

4

Print -1 if pattern not found

After the search loop, add a printf statement to print -1 if the pattern was not found in the text.

DSA C

char text[] = "hello world";
char pattern[] = "world";

int m = strlen(pattern);
int n = strlen(text);

int pattern_hash = 0;
int text_hash = 0;
int h = 1;

int i, j;

for (i = 0; i < m - 1; i++) {
    h = (h * 256) % 101;
}

for (i = 0; i < m; i++) {
    pattern_hash = (256 * pattern_hash + pattern[i]) % 101;
    text_hash = (256 * text_hash + text[i]) % 101;
}

for (i = 0; i <= n - m; i++) {
    if (pattern_hash == text_hash) {
        for (j = 0; j < m; j++) {
            if (text[i + j] != pattern[j])
                break;
        }
        if (j == m) {
            printf("%d\n", i);
            return 0;
        }
    }
    if (i < n - m) {
        text_hash = (256 * (text_hash - text[i] * h) + text[i + m]) % 101;
        if (text_hash < 0)
            text_hash += 101;
    }
}

// Your code here

Hint

If the pattern is not found, print -1. Here the pattern "world" starts at index 6.

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