Rabin Karp String Matching in DSA Rust

Mental Model

We use a number to represent a string and compare these numbers to find matches quickly.

Analogy: Imagine checking if a small book page is inside a big book by comparing page numbers instead of reading every word each time.

Text:  T h i s   i s   a   t e x t
Pattern:     i s   a
Hash:  [hash of 'i s a']
Positions: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

Dry Run Walkthrough

Input: text: 'ababcabc', pattern: 'abc'

Goal: Find all starting positions where 'abc' appears in 'ababcabc'

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

pattern hash = h('abc')
window hash = h('aba')

Why: We need to compare hashes to quickly check for matches

Step 2: Compare pattern hash with window hash at position 0

pattern hash != window hash
window: 'aba' at pos 0

Why: Hashes differ, so no match here

Step 3: Slide window by 1: remove 'a', add 'b', update window hash to h('bab')

window hash = h('bab')
window: 'bab' at pos 1

Why: Update hash efficiently without recomputing whole substring

Step 4: Compare pattern hash with window hash at position 1

pattern hash != window hash
window: 'bab' at pos 1

Why: No match, continue sliding

Step 5: Slide window by 1: remove 'b', add 'c', update window hash to h('abc')

window hash = h('abc')
window: 'abc' at pos 2

Why: Window hash matches pattern hash, possible match

Step 6: Compare actual strings at position 2 to confirm match

text[2..5] = 'abc' matches pattern 'abc'

Why: Hashes can collide, so verify actual strings

Step 7: Slide window by 1: remove 'a', add 'a', update window hash to h('bca')

window hash = h('bca')
window: 'bca' at pos 3

Why: Continue searching for other matches

Step 8: Slide window by 1: remove 'b', add 'b', update window hash to h('cab')

window hash = h('cab')
window: 'cab' at pos 4

Why: Continue searching

Step 9: Slide window by 1: remove 'c', add 'c', update window hash to h('abc')

window hash = h('abc')
window: 'abc' at pos 5

Why: Window hash matches pattern hash again

Step 10: Compare actual strings at position 5 to confirm match

text[5..8] = 'abc' matches pattern 'abc'

Why: Confirm match to avoid false positive

Result:

Matches found at positions 2 and 5
Final matched substrings: 'abc' at pos 2, 'abc' at pos 5

Annotated Code

DSA Rust

fn rabin_karp(text: &str, pattern: &str) -> Vec<usize> {
    let n = text.len();
    let m = pattern.len();
    if m > n || m == 0 {
        return vec![];
    }

    let base: u64 = 256;
    let prime: u64 = 101;

    let mut pattern_hash: u64 = 0;
    let mut window_hash: u64 = 0;
    let mut h: u64 = 1;

    // The value of h would be "pow(base, m-1) % prime"
    for _ in 0..m-1 {
        h = (h * base) % prime;
    }

    // Calculate the hash value of pattern and first window of text
    for i in 0..m {
        pattern_hash = (base * pattern_hash + pattern.as_bytes()[i] as u64) % prime;
        window_hash = (base * window_hash + text.as_bytes()[i] as u64) % prime;
    }

    let mut result = Vec::new();

    // Slide the pattern over text one by one
    for i in 0..=n - m {
        // Check the hash values of current window of text and pattern
        if pattern_hash == window_hash {
            // If the hash values match then only check for characters one by one
            if &text[i..i + m] == pattern {
                result.push(i);
            }
        }

        // Calculate hash value for next window of text: Remove leading digit, add trailing digit
        if i < n - m {
            window_hash = (base * (window_hash + prime - (text.as_bytes()[i] as u64 * h) % prime) + text.as_bytes()[i + m] as u64) % prime;
        }
    }

    result
}

fn main() {
    let text = "ababcabc";
    let pattern = "abc";
    let matches = rabin_karp(text, pattern);
    for pos in matches {
        println!("Match found at index {}", pos);
    }
}

for _ in 0..m-1 { h = (h * base) % prime; }

Calculate h = base^(m-1) mod prime for rolling hash

for i in 0..m { pattern_hash = (base * pattern_hash + pattern.as_bytes()[i] as u64) % prime; window_hash = (base * window_hash + text.as_bytes()[i] as u64) % prime; }

Compute initial hash for pattern and first text window

if pattern_hash == window_hash { if &text[i..i + m] == pattern { result.push(i); } }

If hashes match, verify actual substring to confirm match

if i < n - m { window_hash = (base * (window_hash + prime - (text.as_bytes()[i] as u64 * h) % prime) + text.as_bytes()[i + m] as u64) % prime; }

Update rolling hash by removing left char and adding right char

Output

Match found at index 2

Match found at index 5

Complexity Analysis

Time: O(n + m) on average because we compute hashes in O(m) and slide over text in O(n), with rare full string comparisons

Space: O(1) because we use fixed extra space for hashes and output list proportional to matches

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

Edge Cases

Empty pattern

Returns empty list immediately, no matches

DSA Rust

if m > n || m == 0 {
    return vec![];
}

Pattern longer than text

Returns empty list immediately, no matches

DSA Rust

if m > n || m == 0 {
    return vec![];
}

No matches in text

Returns empty list after full scan

DSA Rust

if pattern_hash == window_hash {
    if &text[i..i + m] == pattern {
        result.push(i);
    }
}

When to Use This Pattern

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

Common Mistakes

Mistake: Not verifying actual substring after hash match, causing false positives
Fix: Always compare the actual substring when hashes match to confirm real match

Mistake: Incorrect rolling hash update causing wrong hash values
Fix: Use modulo arithmetic carefully and remove the leftmost character's contribution correctly

Summary

Finds all occurrences of a pattern in a text using hashing to speed up substring comparisons.

Use when you want faster substring search than naive checking, especially with multiple searches.

The key insight is representing strings as numbers and updating these numbers efficiently as you slide through the text.

Practice

1. What is the main idea behind the Rabin Karp String Matching algorithm?

easy

A. It uses hashing to find pattern matches efficiently in a text.

B. It compares each character of the pattern with the text directly.

C. It sorts the text and pattern before matching.

D. It uses recursion to find all pattern matches.

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.

3. Final Answer:

   It uses hashing to find pattern matches efficiently in a text. -> Option A

4. Quick Check:

   Hashing = Efficient matching [OK]

Hint: Remember: Rabin Karp uses hashing for fast pattern search [OK]

Common Mistakes:

• Thinking it compares characters one by one always
• Confusing it with sorting-based algorithms
• Assuming it uses recursion

2. Which of the following is the correct way to compute the rolling hash in Rabin Karp for the next substring in Rust?

easy

A. hash = (hash - old_char * power) * base + new_char;

B. hash = hash + old_char - new_char * base;

C. hash = (hash + old_char) * base - new_char;

D. hash = (hash * base) - old_char + new_char * power;

Solution

1. Step 1: Recall rolling hash formula

   To move the window, subtract old char's weighted value, multiply by base, add new char.

2. Step 2: Match formula with options

   hash = (hash - old_char * power) * base + new_char; matches the formula: hash = (hash - old_char * power) * base + new_char;

3. Final Answer:

   hash = (hash - old_char * power) * base + new_char; -> Option A

4. Quick Check:

   Rolling hash update = hash = (hash - old_char * power) * base + new_char; [OK]

Hint: Subtract old char, multiply, then add new char [OK]

Common Mistakes:

• Adding old char instead of subtracting
• Wrong order of operations
• Multiplying new char incorrectly

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

let text = "ababc";
let pattern = "abc";
let result = rabin_karp_search(text, pattern);
println!("{:?}", result);

Assume rabin_karp_search returns a vector of starting indices where pattern matches.

medium

A. [0, 2]

B. [1, 3]

C. [2]

D. []

Solution

1. Step 1: Identify pattern occurrences in text

   Text: "ababc"; pattern: "abc"; pattern appears starting at index 2 only.

2. Step 2: Confirm output of search function

   The function returns indices where pattern matches, so output is [2].

3. Final Answer:

   [2] -> Option C

4. Quick Check:

   Pattern at index 2 only [OK]

Hint: Check substring positions carefully [OK]

Common Mistakes:

• Counting overlapping matches incorrectly
• Starting index off by one
• Assuming multiple matches where only one exists

4. Consider this Rust code snippet for Rabin Karp. It does not find any matches even though the pattern exists. What is the bug?

fn rabin_karp_search(text: &str, pattern: &str) -> Vec<usize> {
    let base = 256;
    let prime = 101;
    let m = pattern.len();
    let n = text.len();
    let mut pattern_hash = 0;
    let mut text_hash = 0;
    let mut power = 1;

    for _ in 0..m-1 {
        power = (power * base) % prime;
    }

    for i in 0..m {
        pattern_hash = (base * pattern_hash + pattern.as_bytes()[i] as usize) % prime;
        text_hash = (base * text_hash + text.as_bytes()[i] as usize) % prime;
    }

    let mut result = Vec::new();
    for i in 0..=n-m {
        if pattern_hash == text_hash {
            if &text[i..i+m] == pattern {
                result.push(i);
            }
        }
        if i < n - m {
            text_hash = (base * (text_hash - (text.as_bytes()[i] as usize) * power) + text.as_bytes()[i + m] as usize) % prime;
            if text_hash < 0 {
                text_hash += prime;
            }
        }
    }
    result
}

medium

A. The pattern and text hashes are calculated incorrectly using bytes.

B. The power calculation loop should run from 0 to m, not m-1.

C. The loop should run from 0 to n-m-1, not 0 to n-m.

D. The modulo operation can produce negative values; need to add prime after subtraction.

Solution

1. Step 1: Analyze rolling hash update

   Subtracting (text[i] * power) can cause negative value before modulo.

2. Step 2: Fix negative modulo issue

   Adding prime after subtraction ensures positive modulo result.

3. Final Answer:

   The modulo operation can produce negative values; need to add prime after subtraction. -> Option D

4. Quick Check:

   Modulo negative fix = The modulo operation can produce negative values; need to add prime after subtraction. [OK]

Hint: Add prime after subtraction to avoid negative modulo [OK]

Common Mistakes:

• Ignoring negative modulo results
• Wrong loop ranges for power calculation
• Misusing byte conversions

5. You want to find all occurrences of pattern "aaa" in text "aaaaaa" using Rabin Karp. How many matches will the algorithm find and why?

hard

A. 3 matches, because only non-overlapping occurrences are counted.

B. 4 matches, because overlapping occurrences are counted.

C. 1 match, because repeated characters cause hash collisions.

D. 0 matches, because the algorithm fails on repeated characters.

Solution

1. Step 1: Identify overlapping pattern occurrences

   Text "aaaaaa" contains "aaa" starting at indices 0,1,2,3 (4 matches).

2. Step 2: Rabin Karp counts overlapping matches

   Algorithm checks every substring of length pattern, so all 4 matches are found.

3. Final Answer:

   4 matches, because overlapping occurrences are counted. -> Option B

4. Quick Check:

   Overlapping matches counted = 4 [OK]

Hint: Rabin Karp finds overlapping matches too [OK]

Common Mistakes:

• Assuming only non-overlapping matches count
• Thinking hash collisions prevent matches
• Believing repeated chars cause failure