C Programming: Rabin-Karp Algorithm

Welcome to our comprehensive guide on the Rabin-Karp Algorithm in C programming! In this lesson, we'll dive deep into this powerful string-searching technique. By the end of this tutorial, you'll have a solid understanding of how to use the Rabin-Karp algorithm to find patterns within larger strings.

What is the Rabin-Karp Algorithm?

💡 Pro Tip: The Rabin-Karp Algorithm is a string-searching technique that's used to find a pattern within a larger string. It's particularly useful when the pattern and the text are of different lengths.

📝 Note: The Rabin-Karp Algorithm uses hash functions to calculate the hash value of a string, allowing for efficient pattern searching.

Understanding the Basics

Before we dive into the algorithm, let's cover some essential concepts:

ASCII Values: ASCII (American Standard Code for Information Interchange) is a standard encoding system used to represent text in computers. Each character has a unique numerical value between 0 and 127.
Modulo Operation: The modulo operation (%) returns the remainder of a division operation. For example, 7 % 3 equals 1.

The Rabin-Karp Algorithm Breakdown

The Rabin-Karp Algorithm consists of two main steps:

Preprocessing: Convert the pattern and the text into hash values using a hash function.
Searching: Compare the hash values of the pattern and the text and, if they match, check for a potential match.

Let's dive deeper into each step.

Preprocessing

Here's where we'll create a hash function and calculate the hash values for both the pattern and the text. We'll use the following steps:

Define a prime number, P, to use in our hash function.
Initialize the pattern and text hash values as 0.
Iterate through the pattern and text characters, calculating the hash values using the following formula:

c
Hash[i] = (Hash[i-1] * P + pattern[i]) % modulus

modulus is a large number used to reduce the possibility of hash collisions. A common choice is 10^9 + 9.
Once the hash values for the pattern and the text are calculated, we're ready for the searching step.

Searching

During the searching step, we'll slide a window of size equal to the pattern's length along the text, comparing the hash values of the pattern and the corresponding text window.

Initialize two variables: i (the starting index of the text window) and j (the ending index of the text window, equal to the pattern's length).
Calculate the text window's hash value using the preprocessing formula.
Compare the hash values of the pattern and the text window. If they match, check for a potential match by comparing the characters of the pattern and the text window character-by-character.
If the characters match, we have a potential match. If not, slide the window to the right by one character and repeat the process.
Continue sliding the window until the end of the text is reached.

📝 Note: It's essential to handle hash collisions and character mismatches carefully to ensure that no potential matches are missed.

Example Implementation

Here's a complete example of the Rabin-Karp Algorithm in C:

#include <stdio.h>
#include <stdlib.h>

#define PRIME 101
#define MODULUS (1LL << 32)

long long int hash(char *str, int len) {
    long long int hash = 0;
    for (int i = 0; i < len; ++i)
        hash = (hash * PRIME + str[i]) % MODULUS;
    return hash;
}

void search(char *text, char *pattern) {
    int len_text = strlen(text);
    int len_pattern = strlen(pattern);

    long long int pattern_hash = hash(pattern, len_pattern);
    long long int text_hash = 0;

    for (int i = 0; i < len_pattern; ++i) {
        text_hash = (text_hash * PRIME + text[i]) % MODULUS;
        if (i >= len_pattern - 1) {
            long long int pattern_text_hash_diff = pattern_hash - text_hash;
            if (pattern_text_hash_diff < 0)
                pattern_text_hash_diff += MODULUS;

            if (pattern_text_hash_diff == pattern_hash) {
                int j;
                for (j = 0; j < len_pattern; ++j)
                    if (text[j] != pattern[j])
                        break;
                if (j == len_pattern)
                    printf("Pattern found at index %d\n", i - len_pattern + 1);
            }

            text_hash = (text_hash * PRIME - text[i - len_pattern + 1] + MODULUS) % MODULUS;
        }
        ++i;
    }
}

int main() {
    char text[] = "abababababababcab";
    char pattern[] = "ababc";
    search(text, pattern);
    return 0;
}

🎯 Quiz: What is the output of the example code when run?

A: 5
B: Pattern found at index 2
C: Pattern found at index 3
Correct: B
Explanation: The pattern "ababc" is found at index 2 (position 3-7) in the text "abababababababcab".

Wrapping Up

We've covered the Rabin-Karp Algorithm, a powerful string-searching technique that finds patterns within larger strings. By understanding its inner workings and implementing it in C, you'll be well-equipped to tackle real-world problems involving string matching.

Stay tuned for more advanced topics and keep coding! 😄