Rabin Karp String Matching in DSA Go - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to calculate the initial hash value for the pattern.

DSA Go

var patternHash int
for i := 0; i < len(pattern); i++ {
    patternHash = (patternHash*[1] + int(pattern[i])) % prime
}

Drag options to blanks, or click blank then click option'

A128

B256

C512

D1024

Attempts:

3 left

💡 Hint

Common Mistakes

Using a base value smaller than 256 causes incorrect hash calculations.

Forgetting to use modulo operation to keep hash values manageable.

The base value 256 is used because it covers all ASCII characters for hashing.

2fill in blank

medium

Complete the code to update the rolling hash when sliding the window over the text.

DSA Go

textHash = (textHash - int(text[i])*h) * [1] + int(text[i+len(pattern)])
textHash %= prime
if textHash < 0 {
    textHash += prime
}

Drag options to blanks, or click blank then click option'

A256

B128

C512

D1024

Attempts:

3 left

💡 Hint

Common Mistakes

Using a different base than initial hash causes mismatch.

Not adjusting negative hash values after modulo.

The base 256 is used consistently for rolling hash updates.

3fill in blank

hard

Fix the error in the code that calculates the value of h (the highest power of base).

DSA Go

h := 1
for i := 0; i < len(pattern)-1; i++ {
    h = (h * [1]) % prime
}

Drag options to blanks, or click blank then click option'

A512

B1024

C256

D128

Attempts:

3 left

💡 Hint

Common Mistakes

Using a wrong base value for h causes incorrect rolling hash updates.

Not applying modulo operation inside the loop.

The base 256 is used to calculate h for the rolling hash correctly.

4fill in blank

hard

Fill both blanks to complete the substring comparison after hash match.

DSA Go

if patternHash == textHash {
    match := true
    for j := 0; j < len(pattern); j++ {
        if text[i+[1]] != pattern[[2]] {
            match = false
            break
        }
    }
    if match {
        fmt.Println("Pattern found at index", i)
    }
}

Drag options to blanks, or click blank then click option'

Aj

Bi

C0

Dlen(pattern)

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong indices causes incorrect substring comparison.

Comparing text[i] with pattern[i] instead of offset by j.

We compare characters at offset j in both text and pattern to verify the match.

5fill in blank

hard

Fill all three blanks to complete the main Rabin-Karp search function.

DSA Go

func rabinKarpSearch(text, pattern string, prime int) {
    m := len(pattern)
    n := len(text)
    h := 1
    for i := 0; i < m-1; i++ {
        h = (h * [1]) % prime
    }
    patternHash, textHash := 0, 0
    for i := 0; i < m; i++ {
        patternHash = (patternHash*[2] + int(pattern[i])) % prime
        textHash = (textHash*[2] + int(text[i])) % prime
    }
    for i := 0; i <= n-m; i++ {
        if patternHash == textHash {
            match := true
            for j := 0; j < m; j++ {
                if text[i+j] != pattern[j] {
                    match = false
                    break
                }
            }
            if match {
                fmt.Println("Pattern found at index", i)
            }
        }
        if i < n-m {
            textHash = (textHash - int(text[i])*h) * [3] + int(text[i+m])
            textHash %= prime
            if textHash < 0 {
                textHash += prime
            }
        }
    }
}

Drag options to blanks, or click blank then click option'

A128

B256

C512

D1024

Attempts:

3 left

💡 Hint

Common Mistakes

Mixing different base values causes hash mismatches.

Forgetting modulo operation after hash updates.

The base 256 is consistently used for hashing and rolling hash updates.

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