Rabin Karp String Matching in DSA Rust - Time & Space Complexity

Time Complexity: Rabin Karp String Matching

O(n + m)

Understanding Time Complexity

We want to understand how the Rabin Karp algorithm's running time changes as the text and pattern sizes grow.

Specifically, how many steps does it take to find a pattern in a text?

Scenario Under Consideration

Analyze the time complexity of the following Rabin Karp code snippet.

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

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

    for i in 0..m {
        pattern_hash = (base * pattern_hash + pattern.as_bytes()[i] as u64) % prime;
        text_hash = (base * text_hash + text.as_bytes()[i] as u64) % 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 + prime - h * text.as_bytes()[i] as u64 % prime) + text.as_bytes()[i + m] as u64) % prime;
        }
    }
    result
}
    

This code finds all starting positions where the pattern appears in the text using hashing.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Loop sliding over the text from 0 to n-m to compare hashes and possibly strings.
• How many times: Approximately n-m+1 times, which grows linearly with text size n.

How Execution Grows With Input

As the text length n grows, the algorithm checks more positions, so the work grows roughly in a straight line.

Input Size (n)	Approx. Operations
10	About 10 checks
100	About 100 checks
1000	About 1000 checks

Pattern observation: The number of steps grows directly with the size of the text.

Final Time Complexity

Time Complexity: O(n + m)

This means the time to find the pattern grows roughly in a straight line with the combined size of text and pattern.

Common Mistake

[X] Wrong: "Rabin Karp always runs in constant time because it uses hashing."

[OK] Correct: Hashing helps speed up comparisons, but the algorithm still checks many positions, so time grows with input size.

Interview Connect

Understanding Rabin Karp's time complexity shows you can analyze how hashing helps speed up searching, a useful skill for many coding problems.

Self-Check

"What if we used a larger prime number for hashing? How would the time complexity change?"

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