Rabin Karp String Matching in DSA Go - Build from Scratch

Rabin Karp String Matching

📖 Scenario: You are building a simple text search tool that finds if a small pattern exists inside a larger text. This is useful in searching documents, logs, or DNA sequences.

🎯 Goal: Build a program that uses the Rabin Karp algorithm to check if a given pattern exists in a text and prints the starting index of the first match or -1 if not found.

📋 What You'll Learn

Create a string variable text with the value "abracadabra"

Create a string variable pattern with the value "cada"

Create an integer variable prime with the value 101 to use as a prime number for hashing

Write a function rabinKarpSearch(text string, pattern string, prime int) int that returns the starting index of the first match or -1 if no match

Print the result of calling rabinKarpSearch(text, pattern, prime)

💡 Why This Matters

🌍 Real World

Text search is used in search engines, document editors, and bioinformatics to find patterns quickly.

💼 Career

Understanding string matching algorithms like Rabin Karp is important for software engineers working on search features, data processing, and optimization.

1

Create the text and pattern strings

Create a string variable called text with the value "abracadabra" and a string variable called pattern with the value "cada".

DSA Go

# Create the text and pattern strings

// Your code here

Hint

Use text := "abracadabra" and pattern := "cada" to create the variables.

2

Add the prime number for hashing

Add an integer variable called prime and set it to 101 to use as the prime number for hashing.

DSA Go

package main

func main() {
    text := "abracadabra"
    pattern := "cada"
    
    // Your code here
}

Hint

Use prime := 101 to create the prime number variable.

3

Write the Rabin Karp search function

Write a function called rabinKarpSearch with parameters text string, pattern string, and prime int that returns an int. Implement the Rabin Karp algorithm to find the first index of pattern in text or return -1 if not found.

DSA Go

package main

func main() {
    text := "abracadabra"
    pattern := "cada"
    prime := 101
}

// Your code here: Write rabinKarpSearch function

Hint

Use the Rabin Karp algorithm steps: calculate initial hashes, slide over text, compare hashes, and check characters if hashes match.

4

Print the search result

Print the result of calling rabinKarpSearch(text, pattern, prime) inside the main function.

DSA Go

package main

import "fmt"

func rabinKarpSearch(text string, pattern string, prime int) int {
    // Rabin Karp implementation
}

func main() {
    text := "abracadabra"
    pattern := "cada"
    prime := 101

    // Your code here
}

Hint

Use fmt.Println(result) to print the index returned by rabinKarpSearch.

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