Rabin Karp String Matching in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Rabin Karp hash calculation

What is the output of the following Go code that calculates the initial hash of the pattern "abc" using a simple rolling hash with base 256 and modulo 101?

DSA Go

package main
import "fmt"
func main() {
    pattern := "abc"
    base := 256
    mod := 101
    hash := 0
    for i := 0; i < len(pattern); i++ {
        hash = (hash*base + int(pattern[i])) % mod
    }
    fmt.Println(hash)
}

A 24

B 56

C 12

D 90

💡 Hint

Calculate hash step by step: ((0*256 + 'a') % 101), then ((prev*256 + 'b') % 101), then ((prev*256 + 'c') % 101).

The hash is calculated as (((0*256 + 97) % 101)*256 + 98) % 101)*256 + 99) % 101 = 90.

❓ Predict Output

intermediate

Rabin Karp rolling hash update output

Given the initial hash of substring "abc" is 90, base 256, modulo 101, and the highest power h = 256^2 % 101 = 88, what is the new hash after sliding the window to substring "bcd" (removing 'a', adding 'd')?

DSA Go

package main
import "fmt"
func main() {
    oldHash := 90
    base := 256
    mod := 101
    h := 88
    oldChar := 'a'
    newChar := 'd'
    newHash := (oldHash - int(oldChar)*h)*base + int(newChar)
    newHash = newHash % mod
    if newHash < 0 {
        newHash += mod
    }
    fmt.Println(newHash)
}

A 31

B 56

C 12

D 94

💡 Hint

Use formula: newHash = ((oldHash - oldChar*h)*base + newChar) % mod

Calculate: (90 - 97*88)*256 + 100 mod 101 = (90 - 8536)*256 + 100 mod 101 = (-8446)*256 + 100 mod 101 = -2162176 + 100 mod 101 = -2162076 mod 101 = 31

🧠 Conceptual

advanced

Why use modulo in Rabin Karp hashing?

Why is modulo operation used in the Rabin Karp algorithm's hash calculations?

A To keep hash values within a fixed range and avoid integer overflow

B To make the hash values unique for every substring

C To speed up the string comparison step

D To convert characters into numbers

💡 Hint

Think about what happens if numbers get too big in calculations.

Modulo keeps hash values within a fixed range, preventing overflow and making calculations manageable.

🔧 Debug

advanced

Identify the bug in this Rabin Karp hash update code

What error will this Go code produce when updating the rolling hash in Rabin Karp algorithm?

DSA Go

oldHash := 90
base := 256
mod := 101
h := 88
oldChar := 'a'
newChar := 'd'
newHash := (oldHash - int(oldChar)*h)*base + int(newChar)
newHash = newHash % mod
fmt.Println(newHash)

A Runtime panic due to integer overflow

B No error, prints correct hash value

C Prints negative hash value

D Compilation error due to missing import

💡 Hint

Check if negative values are handled after modulo operation.

The code does not handle negative values after modulo, so newHash can be negative when printed.

🚀 Application

expert

Number of pattern matches found by Rabin Karp

Given the text "abracadabra" and pattern "abra", how many times will the Rabin Karp algorithm find the pattern in the text?

A 3

B 2

C 1

D 4

💡 Hint

Look for all occurrences of "abra" in "abracadabra".

The pattern "abra" appears twice: at the start (index 0) and near the end (index 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