Rabin Karp String Matching in DSA C++ - Execution Trace

Concept Flow - Rabin Karp String Matching

Start

↓

Calculate pattern hash

↓

Calculate initial window hash in text

↓

For each window in text

↓

Compare hashes

↓

Check exact chars

↓

Match found

↓

End

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

Execution Sample

DSA C++

pattern = "abc"
text = "abdacbcabc"
pattern_hash = hash("abc")
window_hash = hash(text[0:3])
for i in range(len(text)-len(pattern)+1):
  if window_hash == pattern_hash:
    # check chars
  # update window_hash for next window

This code slides a window over the text, compares hash values to find pattern matches.

Execution Table

Step	Operation	Window Start Index	Window Text	Window Hash	Pattern Hash	Hash Match?	Exact Match Check	Match Found	Visual State
1	Calculate pattern hash	-	-	2946	2946	N/A	N/A	N/A	"abc" pattern hash = 2946
2	Calculate initial window hash	0	abd	2944	2946	No	No check	No	Window: abd (2944) != pattern (2946)
3	Slide window	1	bda	2945	2946	No	No check	No	Window: bda (2945) != pattern (2946)
4	Slide window	2	dac	2947	2946	No	No check	No	Window: dac (2947) != pattern (2946)
5	Slide window	3	acb	2945	2946	No	No check	No	Window: acb (2945) != pattern (2946)
6	Slide window	4	cbc	2947	2946	No	No check	No	Window: cbc (2947) != pattern (2946)
7	Slide window	5	bca	2945	2946	No	No check	No	Window: bca (2945) != pattern (2946)
8	Slide window	6	cab	2947	2946	No	No check	No	Window: cab (2947) != pattern (2946)
9	Slide window	7	abc	2946	2946	Yes	Check chars	Yes	Window: abc matches pattern hash, chars match
10	End	-	-	-	-	-	-	-	All windows checked

💡 All windows processed; last window matched pattern exactly.

Variable Tracker

Variable	Start	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	N/A	2946	2946	2946	2946	2946	2946	2946	2946	2946
window_hash	N/A	2944	2945	2947	2945	2947	2945	2947	2946	2946
window_start_index	0	0	1	2	3	4	5	6	7	7
match_found	No	No	No	No	No	No	No	No	Yes	Yes

Key Moments - 3 Insights

Why do we compare hashes before checking characters?

Because comparing hashes is faster; only if hashes match do we check characters to confirm, as shown in step 9 of the execution_table.

Why do some window hashes not match the pattern hash even if characters are similar?

Because the hash function produces different values for different strings; for example, 'abd' and 'abc' have different hashes (steps 2 and 9).

How is the window hash updated efficiently when sliding?

The window hash is updated by removing the leftmost character's contribution and adding the new rightmost character's contribution, avoiding full recomputation, as implied between steps.

Visual Quiz - 3 Questions

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

A 2945

B 2947

C 2946

D 2944

💡 Hint

Check the 'Window Hash' column for step 5 in the execution_table.

At which step does the hash match and exact character check confirm a match?

A Step 7

B Step 9

C Step 2

D Step 4

💡 Hint

Look for 'Hash Match?' = Yes and 'Exact Match Check' = Check chars in the execution_table.

If the pattern was "abd" instead of "abc", which step would likely show a match?

A Step 2

B Step 9

C Step 5

D Step 1

💡 Hint

Compare the window text and hashes in the execution_table; 'abd' appears at step 2.

Concept Snapshot

Rabin Karp String Matching:
- Compute hash of pattern and first text window
- Slide window over text, update hash efficiently
- If hashes match, check characters to confirm
- Fast average case by avoiding full comparisons
- Uses rolling hash to update window hash
- Matches found when hash and chars both match

Full Transcript

Rabin Karp algorithm starts by computing the hash of the pattern. Then it computes the hash of the first window in the text. It slides the window one character at a time, updating the hash efficiently without recomputing from scratch. At each step, it compares the window hash with the pattern hash. If they match, it checks the characters one by one to confirm the match. This process continues until all windows in the text are checked. The algorithm is efficient because it avoids unnecessary character comparisons by using hash comparisons first.

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