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

↓

Check characters one by one

↓

Pattern found

↓

Slide window

↓

Repeat until end of text

This flow shows how Rabin Karp computes hashes for the pattern and text windows, compares them, verifies matches, and slides the window through the text.

Execution Sample

DSA Go

pattern := "abc"
text := "abdabcbabc"

// Compute pattern hash
// Slide window over text
// Compare hashes and verify matches

This code tries to find all occurrences of "abc" in the text "abdabcbabc" using Rabin Karp.

Execution Table

Step	Operation	Pattern Hash	Window Start Index	Window Hash	Hash Match?	Character Check	Match Found	Visual State
1	Compute pattern hash	294	-	-	-	-	-	Pattern: 'abc' hash=294
2	Compute initial window hash	-	0	294	-	-	-	Text window: 'abd' hash=294
3	Compare hashes	294	0	294	Yes	-	-	Hashes match, check characters
4	Check characters	-	0	-	-	No	No	Window 'abd' != pattern on char check
5	Slide window	-	1	293	-	-	-	Window slides to 'bda' hash=293
6	Compare hashes	294	1	293	No	-	No	Window 'bda' != pattern
7	Slide window	-	2	291	-	-	-	Window slides to 'dab' hash=291
8	Compare hashes	294	2	291	No	-	No	Window 'dab' != pattern
9	Slide window	-	3	294	-	-	-	Window slides to 'abc' hash=294
10	Compare hashes	294	3	294	Yes	-	-	Hashes match, check characters
11	Check characters	-	3	-	-	Yes	Yes	Window 'abc' matches pattern
12	Slide window	-	4	292	-	-	-	Window slides to 'bcb' hash=292
13	Compare hashes	294	4	292	No	-	No	Window 'bcb' != pattern
14	Slide window	-	5	294	-	-	-	Window slides to 'cba' hash=294
15	Compare hashes	294	5	294	Yes	-	-	Hashes match, check characters
16	Check characters	-	5	-	-	No	No	Window 'cba' != pattern on char check
17	Slide window	-	6	294	-	-	-	Window slides to 'bab' hash=294
18	Compare hashes	294	6	294	Yes	-	-	Hashes match, check characters
19	Check characters	-	6	-	-	No	No	Window 'bab' != pattern on char check
20	Slide window	-	7	294	-	-	-	Window slides to 'abc' hash=294
21	Compare hashes	294	7	294	Yes	-	-	Hashes match, check characters
22	Check characters	-	7	-	-	Yes	Yes	Window 'abc' matches pattern
23	End	-	-	-	-	-	-	Reached end of text windows

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

Variable Tracker

Variable	Start	After Step 2	After Step 5	After Step 7	After Step 9	After Step 12	After Step 14	After Step 17	After Step 20	Final
pattern_hash	-	294	294	294	294	294	294	294	294	294
window_start_index	-	0	1	2	3	4	5	6	7	-
window_hash	-	294	293	291	294	292	294	294	294	-
match_found	-	No	No	No	Yes	No	No	No	Yes	-

Key Moments - 3 Insights

Why do we check characters one by one even if the hashes match?

Because different strings can have the same hash (hash collision). So after hash match (see steps 3, 10, 15, 18, 21), we verify characters to confirm actual match.

Why do we slide the window even when hashes don't match?

Because the pattern might appear later in the text. Sliding the window (steps 5, 7, 9, etc.) moves to the next substring to check.

How is the window hash updated efficiently when sliding?

Instead of recomputing from scratch, the hash is updated by removing the leftmost character and adding the new rightmost character (rolling hash). This is why window_hash changes stepwise (see variable_tracker).

Visual Quiz - 3 Questions

Look at the execution table at step 3. What happens when the pattern hash equals the window hash?

A We immediately declare a match without further checks.

B We check characters one by one to confirm the match.

C We slide the window to the next position.

D We recompute the pattern hash.

💡 Hint

Refer to step 3 and 4 in the execution_table where hash match leads to character check.

At which window start index does the first actual pattern match occur according to the execution table?

A 0

B 2

C 3

D 7

💡 Hint

Check the 'Match Found' column in execution_table rows for 'Yes' and note the window start index.

If the pattern was changed to 'abd', how would the pattern hash in variable_tracker change after step 2?

A It would remain 294.

B It would become 294.

C It would become 293.

D It would become 292.

💡 Hint

Look at the window hash for 'abd' at step 2 in execution_table and relate it to pattern hash.

Concept Snapshot

Rabin Karp String Matching:
- Compute hash of pattern and initial text window
- Slide window over text, updating hash efficiently
- If hashes match, verify characters one by one
- Use rolling hash to avoid recomputing full hash
- Detect pattern occurrences by matching hashes and characters

Full Transcript

Rabin Karp string matching works by computing a numeric hash for the pattern and for each substring window in the text. It slides the window one character at a time, updating the hash efficiently using a rolling hash method. When the hash of the current window matches the pattern hash, it checks characters one by one to confirm the match because different strings can have the same hash. This process continues until all possible windows in the text are checked. The example shows pattern 'abc' searched in 'abdabcbabc' with matches found at indices 3 and 7.

Practice

1. What is the main advantage of the Rabin Karp string matching algorithm compared to a simple brute force search?

easy

A. It uses hashing to quickly find potential matches before checking characters

B. It sorts the text before searching

C. It uses recursion to find matches

D. It only works on numeric strings

Solution

1. Step 1: Understand Rabin Karp's approach

   Rabin Karp uses a hash function to convert substrings into numbers for quick comparison.

2. Step 2: Compare with brute force

   Brute force checks each character one by one, while Rabin Karp first compares hash values to skip unnecessary checks.

3. Final Answer:

   It uses hashing to quickly find potential matches before checking characters -> Option A

4. Quick Check:

   Hashing speeds up matching = A [OK]

Hint: Remember: Rabin Karp uses hashing to speed up matching [OK]

Common Mistakes:

• Thinking Rabin Karp sorts the text
• Assuming it uses recursion
• Believing it only works on numbers

2. Which of the following is the correct way to compute the initial hash of a substring in Rabin Karp algorithm in Go?

easy

A. hash = hash + int(char) * base ^ index

B. hash = (hash*base + int(char)) % prime

C. hash = int(char) * prime + base

D. hash = base % int(char) + prime

Solution

1. Step 1: Recall hash calculation formula

   The rolling hash is computed as (previous_hash * base + current_char) mod prime.

2. Step 2: Match formula with options

   hash = (hash*base + int(char)) % prime matches the correct formula for rolling hash calculation.

3. Final Answer:

   hash = (hash*base + int(char)) % prime -> Option B

4. Quick Check:

   Rolling hash formula = A [OK]

Hint: Rolling hash = (prev_hash * base + char) mod prime [OK]

Common Mistakes:

• Using addition instead of multiplication for rolling hash
• Mixing up base and prime positions
• Using XOR (^) instead of power or multiplication

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

package main
import "fmt"
func main() {
  text := "ababc"
  pattern := "abc"
  // Simplified hash values for illustration
  patternHash := 294
  textHash := 0
  base := 256
  prime := 101
  for i := 0; i <= len(text)-len(pattern); i++ {
    if i == 0 {
      for j := 0; j < len(pattern); j++ {
        textHash = (textHash*base + int(text[j])) % prime
      }
    } else {
      textHash = (base*(textHash-int(text[i-1])*intPow(base, len(pattern)-1)) + int(text[i+len(pattern)-1])) % prime
      if textHash < 0 {
        textHash += prime
      }
    }
    if textHash == patternHash {
      fmt.Println("Pattern found at index", i)
    }
  }
}

func intPow(a, b int) int {
  result := 1
  for b > 0 {
    result *= a
    b--
  }
  return result
}

medium

A. Pattern found at index 1

B. Pattern found at index 0

C. Pattern found at index 2

D. No pattern found

Solution

1. Step 1: i=0, substring "aba"

   Initial textHash computed with sequential (textHash*base + char) % 101, resulting in value <101 !=294. No print.

2. Step 2: i=1, substring "bab"

   Rolling hash: (base*(textHash - text[i-1]*base^{2}) + newchar) % 101, normalized if negative, so 0-100 !=294. No print.

3. Step 3: i=2, substring "abc"

   Similarly, textHash after %101 (and +prime if <0) is 0-100 !=294. No print.

4. Final Answer:

   No pattern found -> Option D

5. Quick Check:

   textHash always %101 <101, patternHash=294 >101, no match = D [OK]

Hint: Check rolling hash matches pattern hash to find index fast [OK]

Common Mistakes:

• Assuming match at index 0 without hash check
• Forgetting to adjust negative hash values
• Incorrect rolling hash update

4. Identify the bug in this Rabin Karp implementation snippet in Go:

textHash = (base*(textHash-int(text[i-1])*intPow(base, len(pattern))) + int(text[i+len(pattern)-1])) % prime

What is the issue?

medium

A. The base should be added, not multiplied

B. The modulo prime is missing

C. The power used in intPow should be len(pattern)-1, not len(pattern)

D. The subtraction of int(text[i-1]) is incorrect

Solution

1. Step 1: Understand rolling hash update formula

   The correct formula uses base^(pattern_length-1) to remove the leftmost character's contribution.

2. Step 2: Check the power used in intPow

   The code uses len(pattern), which is one too many, causing wrong hash calculation.

3. Final Answer:

   The power used in intPow should be len(pattern)-1, not len(pattern) -> Option C

4. Quick Check:

   Power = pattern length minus one [OK]

Hint: Use len(pattern)-1 as power when removing left char hash [OK]

Common Mistakes:

• Using full pattern length power instead of one less
• Forgetting modulo operation
• Incorrect subtraction of character value

5. You want to find all occurrences of pattern "test" in a very long text using Rabin Karp. Which approach best reduces the chance of false positives caused by hash collisions?

hard

A. Use a large prime number and verify matches by direct string comparison

B. Use a small prime number to speed up hashing

C. Skip direct string comparison and rely only on hash matches

D. Use base 1 for hashing to simplify calculations

Solution

1. Step 1: Understand hash collisions in Rabin Karp

   Different substrings can have the same hash value, causing false positives.

2. Step 2: Best practice to reduce false positives

   Use a large prime to reduce collisions and verify matches by comparing actual substrings.

3. Final Answer:

   Use a large prime number and verify matches by direct string comparison -> Option A

4. Quick Check:

   Large prime + verify strings = D [OK]

Hint: Always verify substring after hash match to avoid false positives [OK]

Common Mistakes:

• Using small primes increasing collisions
• Skipping substring verification
• Using base 1 which causes poor hashing