Why Rabin Karp String Matching in DSA C?

The Big Idea

What if you could find any phrase in a huge book almost instantly without reading every word?

The Scenario

Imagine you have a huge book and you want to find every place where a short phrase appears. You try reading every word and comparing it to your phrase by hand.

The Problem

This manual way is very slow and tiring. You keep checking each word one by one, and if the book is very long, it takes forever. You might also make mistakes by missing some matches or checking the same parts again and again.

The Solution

Rabin Karp uses a clever math trick called hashing to quickly check if parts of the book might match your phrase. Instead of comparing every letter, it compares numbers that represent the words. This makes searching much faster and less error-prone.

Before vs After

✗ Before

for (int i = 0; i <= text_length - pattern_length; i++) {
    int j;
    for (j = 0; j < pattern_length; j++) {
        if (text[i + j] != pattern[j]) break;
    }
    if (j == pattern_length) printf("Match at %d\n", i);
}

✓ After

int pattern_hash = compute_hash(pattern, pattern_length);
int text_hash = compute_hash(text, pattern_length);
for (int i = 0; i <= text_length - pattern_length; i++) {
    if (pattern_hash == text_hash && compare_strings(text + i, pattern, pattern_length)) {
        printf("Match at %d\n", i);
    }
    if (i < text_length - pattern_length) {
        text_hash = roll_hash(text_hash, text[i], text[i + pattern_length]);
    }
}

What It Enables

It enables fast and efficient searching of patterns in large texts by turning strings into numbers for quick comparison.

Real Life Example

Finding a specific word or phrase in a large document, like searching for a name in thousands of pages of legal documents instantly.

Key Takeaways

Manual checking is slow and error-prone for large texts.

Rabin Karp uses hashing to speed up pattern searching.

This method makes searching large texts fast and reliable.