Rabin Karp String Matching in DSA Rust - Execution Trace

Concept Flow - Rabin Karp String Matching

Compute pattern hash

↓

Compute initial text window hash

↓

For each text window

↓

Compare pattern hash and window hash?

No→Slide window: update hash

|Yes↓

Check characters one by one

↓

Match found?

No→Slide window: update hash

Yes↓

Report match

↓

Repeat until end of text

The algorithm computes a hash for the pattern and for each window of text, compares hashes, and if equal, checks characters to confirm match.

Execution Sample

DSA Rust

pattern = "abc"
text = "abdabcbabc"
pattern_hash = hash("abc")
window_hash = hash(text[0..3])
for i in 0..=text.len()-pattern.len() {
  if pattern_hash == window_hash { check chars }
  update window_hash
}

This code slides a window over the text, compares hash values with the pattern hash, and confirms matches by character comparison.

Execution Table

Step	Operation	Window Start Index	Window Text	Window Hash	Pattern Hash	Hash Match?	Character Check	Match Found?	Action
1	Compute pattern hash	-	-	2946	2946	N/A	N/A	N/A	Pattern hash computed
2	Compute initial window hash	0	abd	2937	2946	No	N/A	No	Slide window
3	Slide window	1	bda	2940	2946	No	N/A	No	Slide window
4	Slide window	2	dab	2943	2946	No	N/A	No	Slide window
5	Slide window	3	abc	2946	2946	Yes	Compare 'abc' with 'abc'	Yes	Report match at index 3
6	Slide window	4	bcb	2947	2946	No	N/A	No	Slide window
7	Slide window	5	cba	2945	2946	No	N/A	No	Slide window
8	Slide window	6	bab	2943	2946	No	N/A	No	Slide window
9	Slide window	7	abc	2946	2946	Yes	Compare 'abc' with 'abc'	Yes	Report match at index 7
10	End	-	-	-	-	-	-	-	Reached end of text windows

💡 Reached end of text windows after checking all possible positions

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	After Step 9	Final
pattern_hash	-	2946	2946	2946	2946	2946	2946	2946	2946	2946	2946
window_hash	-	-	2937	2940	2943	2946	2947	2945	2943	2946	2946
window_start_index	-	-	0	1	2	3	4	5	6	7	-
match_found	-	-	No	No	No	Yes	No	No	No	Yes	-

Key Moments - 3 Insights

Why do we compare characters even if the hash matches?

Because different strings can have the same hash (hash collision). The character check confirms the actual match, as shown in steps 5 and 9 in the execution_table.

How is the window hash updated efficiently when sliding?

The hash is updated by removing the leftmost character's contribution and adding the new rightmost character's contribution, avoiding recomputing the whole hash, as implied in the 'Slide window' actions in the execution_table.

Why does the algorithm stop after the window reaches the end of the text?

Because no further windows of pattern length can fit beyond that point, as indicated in step 10 'End' in the execution_table.

Visual Quiz - 3 Questions

Look at the execution_table, what is the window text at step 5?

A bcb

B abc

C dab

D bab

💡 Hint

Check the 'Window Text' column at step 5 in the execution_table.

At which step does the first match get reported?

A Step 3

B Step 7

C Step 5

D Step 9

💡 Hint

Look for 'Report match' in the 'Action' column in the execution_table.

If the pattern hash was different, how would the 'Hash Match?' column change?

A All 'No'

B All 'Yes'

C Alternating 'Yes' and 'No'

D No change

💡 Hint

If pattern hash differs, no window hash can match it, so 'Hash Match?' would always be 'No' as per execution_table logic.

Concept Snapshot

Rabin Karp String Matching:
- Compute hash of pattern and initial text window
- Slide window over text, update hash efficiently
- If hashes match, check characters to confirm
- Report match if confirmed
- Stops when window reaches text end

Full Transcript

Rabin Karp string matching works by computing a hash value for the pattern and for each substring window of the text with the same length. It slides this window across the text, updating the hash efficiently by removing the leftmost character and adding the new rightmost character. When the hash of the current window matches the pattern hash, it compares characters one by one to confirm the match, because different strings can have the same hash. Matches are reported when confirmed. The process stops when the window reaches the end of the text and no further windows of pattern length remain.

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