Rabin Karp String Matching in DSA C++

Mental Model

We use a number to represent a string and slide over the text to find matches quickly by comparing these numbers instead of characters.

Analogy: Imagine checking if a small picture appears inside a big picture by comparing their color codes instead of looking at every pixel one by one.

Text:  T -> h -> i -> s ->   -> i -> s ->   -> a ->   -> t -> e -> x -> t -> null
Pattern:           P -> a -> t -> t -> e -> r -> n -> null
Hash:    [hash of pattern] and sliding hash over text positions

Dry Run Walkthrough

Input: text: "ababc", pattern: "abc"

Goal: Find the starting index where pattern "abc" appears in text "ababc"

Step 1: Calculate hash of pattern "abc" and first window "aba" in text

pattern hash = hash("abc") = 294
text window hash = hash("aba") = 293

Why: We need to compare hashes to quickly check if pattern matches current text window

Step 2: Compare pattern hash with current window hash; they differ, so slide window by one

text window moves to "bab" with hash = 298

Why: Hashes differ, so pattern does not match here; move to next substring

Step 3: Compare pattern hash with new window hash; they differ, slide window again

text window moves to "abc" with hash = 294

Why: Hashes match, so check characters to confirm

Step 4: Check characters of pattern and text window "abc"; they match exactly

Match found at index 2 in text

Why: Hash collision is rare but possible; character check confirms match

Result:

Final state: Match found at index 2
Text windows: "aba" (293), "bab" (298), "abc" (294)
Answer: 2

Annotated Code

DSA C++

#include <iostream>
#include <string>
using namespace std;

const int d = 256; // number of characters in input alphabet
const int q = 101; // a prime number for modulo

void rabinKarp(const string& text, const string& pattern) {
    int n = text.size();
    int m = pattern.size();
    if (m > n) {
        cout << "No match found" << endl;
        return;
    }

    int p = 0; // hash value for pattern
    int t = 0; // hash value for text window
    int h = 1; // value of d^(m-1) % q

    // Calculate h = pow(d, m-1) % q
    for (int i = 0; i < m - 1; i++) {
        h = (h * d) % q;
    }

    // Calculate initial hash values for pattern and first window
    for (int 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 (int i = 0; i <= n - m; i++) {
        // Check hash values
        if (p == t) {
            // If hash matches, check characters one by one
            int j;
            for (j = 0; j < m; j++) {
                if (text[i + j] != pattern[j])
                    break;
            }
            if (j == m) {
                cout << "Pattern found at index " << i << endl;
                return;
            }
        }

        // Calculate hash for next window
        if (i < n - m) {
            t = (d * (t - text[i] * h) + text[i + m]) % q;
            if (t < 0) t += q;
        }
    }

    cout << "No match found" << endl;
}

int main() {
    string text = "ababc";
    string pattern = "abc";
    rabinKarp(text, pattern);
    return 0;
}

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

Calculate multiplier for highest place value in rolling hash

for (int 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) { ... } }

If hashes match, verify characters to avoid false positive

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

Roll hash forward by removing left char and adding right char

Output

Pattern found at index 2

Complexity Analysis

Time: O(n + m) because we compute initial hashes in O(m) and slide over text in O(n), with rare character checks

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

vs Alternative: Compared to naive O(n*m) matching, Rabin-Karp speeds up by using hash comparisons to skip unnecessary character checks

Edge Cases

pattern longer than text

No match found immediately

DSA C++

if (m > n) { cout << "No match found" << endl; return; }

pattern equals text

Match found at index 0

DSA C++

for (int i = 0; i <= n - m; i++) { ... }

pattern not in text

No match found after full scan

DSA C++

cout << "No match found" << endl;

When to Use This Pattern

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

Common Mistakes

Mistake: Not updating the rolling hash correctly when sliding the window
Fix: Use the formula t = (d * (t - text[i] * h) + text[i + m]) % q and adjust if negative

Mistake: Skipping character-by-character check after hash match
Fix: Always verify characters after hash match to avoid false positives due to hash collisions

Summary

It finds a pattern in a text by comparing hash values of substrings to speed up matching.

Use it when you want faster substring search than checking every character directly.

The key insight is using a rolling hash to quickly update and compare substring hashes.

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 Rabin Karp's approach

   The algorithm uses a hash function to convert the pattern and text substrings into numbers.

2. Step 2: Use hashing for efficient matching

   By comparing hash values instead of characters, it quickly finds potential matches and then verifies them.

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
• Assuming it sorts strings before matching
• Confusing it with recursive search methods

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. Add leftmost char's hash, multiply by base, subtract new char's hash

B. Multiply entire hash by base and add new char's hash only

C. Remove leftmost char's hash, multiply by base, add new char's hash

D. Recalculate hash from scratch for new substring

Solution

1. Step 1: Understand rolling hash update

   Remove the leftmost character's contribution, multiply remaining hash by base, then add new character's value.

2. Step 2: Apply formula for next substring

   This keeps hash calculation efficient without recomputing from scratch.

3. Final Answer:

   Remove leftmost char's hash, multiply by base, add new char's hash -> Option C

4. Quick Check:

   Rolling hash update = Remove + multiply + add [OK]

Hint: Rolling hash = remove old char + shift + add new char [OK]

Common Mistakes:

• Recalculating hash fully each time
• Adding instead of removing old char's hash
• Multiplying after adding new char instead of before

3. What will be the output of the following C++ code snippet using Rabin Karp to find pattern "abc" in text "ababc"?

std::string text = "ababc";
std::string pattern = "abc";
// Assume correct Rabin Karp implementation
std::vector<int> matches = rabinKarpSearch(text, pattern);
for (int pos : matches) std::cout << pos << " ";

medium

A. 1

B. 0 2

C. No output

D. 2

Solution

1. Step 1: Identify pattern occurrences in text

   Pattern "abc" appears starting at index 2 in "ababc" (0-based indexing).

2. Step 2: Confirm no other matches

   Substring at index 0 is "aba", not "abc"; index 1 is "bab", not "abc".

3. Final Answer:

   2 -> Option D

4. Quick Check:

   Pattern found at index 2 [OK]

Hint: Check substring positions carefully for exact matches [OK]

Common Mistakes:

• Assuming match at index 0 incorrectly
• Confusing overlapping substrings
• Using 1-based indexing instead of 0-based

4. Identify the bug in this Rabin Karp rolling hash update snippet:

hash = (hash - text[i] * pow(base, m-1)) * base + text[i+m];

What is the likely problem?

medium

A. Missing modulo operation causing overflow

B. Wrong power used in subtraction term

C. Adding instead of subtracting old char's hash

D. Incorrect base multiplier order

Solution

1. Step 1: Check arithmetic operations in rolling hash

   The formula subtracts old char's hash, multiplies by base, adds new char's value.

2. Step 2: Identify missing modulo usage

   Without modulo, hash values can overflow integer limits causing wrong results.

3. Final Answer:

   Missing modulo operation causing overflow -> Option A

4. Quick Check:

   Modulo needed to prevent overflow [OK]

Hint: Always apply modulo after each hash update [OK]

Common Mistakes:

• Ignoring modulo leading to wrong hash values
• Using wrong power exponent
• Mixing addition and subtraction signs

5. Given a large text and multiple patterns, how can Rabin Karp be adapted to efficiently find all pattern occurrences?

hard

A. Use a combined hash set of all patterns and check text substrings against it

B. Run Rabin Karp separately for each pattern on the entire text

C. Sort all patterns and use binary search on text substrings

D. Use recursion to match patterns one by one

Solution

1. Step 1: Understand multi-pattern matching challenge

   Running Rabin Karp separately for each pattern is inefficient for many patterns.

2. Step 2: Use combined hashing approach

   Hash all patterns and store in a set. Then slide over text, hashing substrings and checking set membership.

3. Step 3: Efficiently find all matches

   This reduces repeated work and speeds up multi-pattern search.

4. Final Answer:

   Use a combined hash set of all patterns and check text substrings against it -> Option A

5. Quick Check:

   Combined hashing = efficient multi-pattern search [OK]

Hint: Hash all patterns once, then check text substrings [OK]

Common Mistakes:

• Running separate searches for each pattern
• Sorting patterns instead of hashing
• Using recursion unnecessarily