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.