Rabin Karp String Matching in DSA Java - 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

↓

Slide window, update hash

↓

Check characters one by one

↓

Report match

↓

Slide window, update hash

↓

End

The algorithm calculates a hash for the pattern and for each window in the text, compares hashes, and if equal, checks characters to find matches.

Execution Sample

DSA Java

pattern = "abc";
text = "abdacbcabc";
patternHash = hash("abc");
windowHash = hash(text.substring(0, 3));
for (int i = 0; i <= text.length() - pattern.length(); i++) {
  if (patternHash == windowHash) {
    // check characters
  }
  // update windowHash for next window
}

This code slides a window over the text, compares hash values with the pattern hash, and checks characters if hashes match.

Execution Table

Step	Operation	Window Start Index	Window Substring	Window Hash	Pattern Hash	Hash Match?	Character Check	Match Found	Visual State
1	Calculate pattern hash	-	-	-	2946	-	-	-	Pattern hash = 2946
2	Calculate initial window hash	0	abd	2947	2946	No	-	No	Window 'abd' hash=2947
3	Slide window	1	bda	2948	2946	No	-	No	Window 'bda' hash=2948
4	Slide window	2	dac	2950	2946	No	-	No	Window 'dac' hash=2950
5	Slide window	3	acb	2947	2946	No	-	No	Window 'acb' hash=2947
6	Slide window	4	cbc	2951	2946	No	-	No	Window 'cbc' hash=2951
7	Slide window	5	bca	2946	2946	Yes	Check chars	No	Window 'bca' hash=2946
8	Slide window	6	cab	2947	2946	No	-	No	Window 'cab' hash=2947
9	Slide window	7	abc	2946	2946	Yes	Check chars	Yes	Window 'abc' hash=2946
10	End	-	-	-	-	-	-	-	Search complete

💡 Reached end of text windows; all possible matches checked.

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
patternHash	-	2946	2946	2946	2946	2946	2946	2946	2946	2946
windowHash	-	2947	2948	2950	2947	2951	2946	2947	2946	-
windowStartIndex	-	0	1	2	3	4	5	6	7	-
matchFound	false	false	false	false	false	false	false	false	true	-

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 steps 7 and 9 in the execution table.

Why do some windows have different hashes even if substrings look similar?

Because the hash depends on character positions and values; small changes cause different hashes, as seen in steps 2 to 6.

Why do we update the window hash instead of recalculating it from scratch?

Updating the hash by removing the old char and adding the new char is efficient and faster, shown by the sliding window updates in each step.

Visual Quiz - 3 Questions

Look at the execution table, what is the window substring at step 7?

A bca

B cab

C abc

D cbc

💡 Hint

Check the 'Window Substring' column at step 7 in the execution table.

At which step does the first hash match occur?

A Step 5

B Step 7

C Step 9

D Step 3

💡 Hint

Look at the 'Hash Match?' column for the first 'Yes' value.

If the pattern was "abd" instead of "abc", which step would have a hash match first?

A Step 2

B Step 4

C Step 6

D Step 9

💡 Hint

Compare the pattern hash with window hashes in the execution table; 'abd' matches window at step 2.

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 one by one
- Report match if all characters equal
- Efficient for multiple pattern searches
- Uses rolling hash to avoid recomputing full hash each time

Full Transcript

Rabin Karp String Matching works by calculating a hash value for the pattern and for each substring window in the text. It slides a window over the text, updating the hash efficiently by removing the old character and adding the new one. When the hash of the current window matches the pattern's hash, it checks characters one by one to confirm a match. This method speeds up searching by avoiding unnecessary character comparisons when hashes differ. The execution table shows each step, the current window substring, its hash, and whether it matches the pattern hash, with character checks done only when hashes match.

Practice

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

easy

A. It sorts the text and pattern before matching

B. It compares each character one by one without hashing

C. It uses hashing to find pattern matches efficiently

D. It uses recursion to find the pattern

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 -> Option C

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 without hashing
• Confusing it with brute force matching
• Assuming it sorts strings before matching

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

easy

A. new_hash = (old_hash - old_char * high_base) * base + new_char

B. new_hash = old_hash + old_char + new_char

C. new_hash = old_hash * old_char - new_char

D. new_hash = old_hash / base + new_char * high_base

Solution

1. Step 1: Recall rolling hash formula

   Rolling hash removes the old char's contribution and adds the new char's value.

2. Step 2: Apply formula correctly

   It subtracts old_char * high_base, multiplies by base, then adds new_char.

3. Final Answer:

   new_hash = (old_hash - old_char * high_base) * base + new_char -> Option A

4. Quick Check:

   Rolling hash formula = new_hash = (old_hash - old_char * high_base) * base + new_char [OK]

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

Common Mistakes:

• Adding old_char instead of subtracting
• Dividing instead of multiplying by base
• Ignoring the high_base multiplier

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

String text = "ababc";
String pattern = "abc";
List<Integer> result = rabinKarpSearch(text, pattern);
System.out.println(result);

Assume rabinKarpSearch returns a list of starting indices where pattern matches.

medium

A. []

B. [0, 2]

C. [1]

D. [2]

Solution

1. Step 1: Identify pattern occurrences in text

   Text: "ababc"; pattern: "abc"; check substrings of length 3: "aba"(0), "bab"(1), "abc"(2).

2. Step 2: Find matching indices

   Only substring starting at index 2 matches "abc".

3. Final Answer:

   [2] -> Option D

4. Quick Check:

   Pattern found at index 2 only [OK]

Hint: Check substrings of pattern length for exact matches [OK]

Common Mistakes:

• Including partial matches like "aba" or "bab"
• Assuming multiple matches without checking substring
• Confusing indices starting at 1 instead of 0

4. Consider this buggy Java snippet for Rabin Karp pattern search:

int base = 256;
int prime = 101;
int highBase = (int) Math.pow(base, pattern.length());
// ... rest of code
// rolling hash update:
currentHash = (currentHash - text.charAt(i) * highBase) * base + text.charAt(i + pattern.length());
currentHash %= prime;

What is the main bug here?

medium

A. highBase should be base^(pattern.length() - 1), not base^pattern.length()

B. Modulo operation should be before subtraction

C. Rolling hash should add old char, not subtract

D. Base should be 128, not 256

Solution

1. Step 1: Check highBase calculation

   High base is used to remove the leftmost character's contribution, so it should be base^(pattern length - 1).

2. Step 2: Identify incorrect power usage

   Using base^(pattern length) removes too much, causing wrong hash updates.

3. Final Answer:

   highBase should be base^(pattern.length() - 1), not base^pattern.length() -> Option A

4. Quick Check:

   Correct highBase power fixes rolling hash [OK]

Hint: Use base^(pattern length - 1) for highBase in rolling hash [OK]

Common Mistakes:

• Using base^pattern.length() instead of base^(pattern.length()-1)
• Ignoring modulo after subtraction
• Confusing addition and subtraction in rolling hash

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. 2, because it skips overlapping matches

B. 4, because overlapping matches are counted

C. 3, because it counts only non-overlapping matches

D. 1, because it stops after first match

Solution

1. Step 1: Identify all substrings of length 3

   Text "aaaaaa" has substrings: "aaa"(0), "aaa"(1), "aaa"(2), "aaa"(3).

2. Step 2: Count overlapping matches

   All these substrings match pattern "aaa", so 4 matches found including overlaps.

3. Final Answer:

   4, because overlapping matches are counted -> Option B

4. Quick Check:

   Overlapping matches count = 4 [OK]

Hint: Rabin Karp counts overlapping matches by sliding one char at a time [OK]

Common Mistakes:

• Assuming matches cannot overlap
• Stopping search after first match
• Counting only non-overlapping matches