Why Rabin Karp String Matching in DSA Go?

The Big Idea

What if you could find a needle in a haystack without checking every straw?

The Scenario

Imagine you have a huge book and you want to find every place where a certain sentence appears. You try to read every word and compare it with your sentence manually.

The Problem

This manual way is very slow and tiring. You might miss some places or make mistakes because you have to check every word one by one, again and again.

The Solution

Rabin Karp uses a clever math trick called hashing to quickly check if parts of the book might match your sentence. It avoids checking every word fully unless it really needs to, saving a lot of time.

Before vs After

✗ Before

for i := 0; i <= len(text)-len(pattern); i++ {
    if text[i:i+len(pattern)] == pattern {
        fmt.Println("Found at", i)
    }
}

✓ After

patternHash := hash(pattern)
textHash := hash(text[0:len(pattern)])
for i := 0; i <= len(text)-len(pattern); i++ {
    if patternHash == textHash && text[i:i+len(pattern)] == pattern {
        fmt.Println("Found at", i)
    }
    if i < len(text)-len(pattern) {
        textHash = rollHash(textHash, text[i], text[i+len(pattern)])
    }
}

What It Enables

It makes searching for patterns in large texts fast and efficient, even when the text is huge.

Real Life Example

Search engines use this method to quickly find words or phrases in billions of web pages.

Key Takeaways

Manual searching is slow and error-prone.

Rabin Karp uses hashing to speed up pattern matching.

This method is great for fast text searching in big data.

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