Rabin Karp String Matching in DSA Go

Mental Model

We use a number to represent a string and compare these numbers to find matches quickly.

Analogy: Imagine you have a secret code for each word, like a barcode. Instead of checking every letter, you just scan the barcode to see if it matches the one you want.

Text:  T h i s   i s   a   t e x t
Hash: [H0]->[H1]->[H2]->[H3]->...->[Hn]
Pattern: a   t e x t
HashP: [HP]

Dry Run Walkthrough

Input: text: 'ababc', pattern: 'abc'

Goal: Find the starting index where 'abc' appears in 'ababc' using Rabin Karp hashing

Step 1: Calculate hash of pattern 'abc'

Pattern hash HP = hash('abc')

Why: We need a number to represent the pattern for quick comparison

Step 2: Calculate initial hash of first 3 characters in text 'aba'

Text window hash HT = hash('aba')

Why: We compare this hash with pattern hash to check for a match

Step 3: Compare HT and HP; they differ, so slide window by one

Window moves to 'bab', recalculate HT

Why: No match yet, so check next substring

Step 4: Calculate hash for 'bab' and compare with HP

HT = hash('bab'), still not equal to HP

Why: Still no match, continue sliding

Step 5: Slide window to 'abc', recalculate HT

HT = hash('abc')

Why: Check if this substring matches pattern

Step 6: HT equals HP, verify characters to confirm match

'abc' matches pattern at index 2

Why: Hashes match, so confirm by direct comparison to avoid false positive

Result:

Final state: 'ababc'
Match found at index 2

Annotated Code

DSA Go

package main

import (
	"fmt"
)

const (
	prime = 101
)

type RabinKarp struct {
	pattern string
	patternHash int
	patternLen int
	prime int
}

func NewRabinKarp(pattern string) *RabinKarp {
	r := &RabinKarp{
		pattern: pattern,
		patternLen: len(pattern),
		prime: prime,
	}
	r.patternHash = r.hash(pattern, r.patternLen)
	return r
}

func (r *RabinKarp) hash(s string, length int) int {
	hash := 0
	for i := 0; i < length; i++ {
		hash = (hash*256 + int(s[i])) % r.prime
	}
	return hash
}

func (r *RabinKarp) Search(text string) int {
	if len(text) < r.patternLen {
		return -1
	}

	textHash := r.hash(text, r.patternLen)
	highestPow := 1
	for i := 0; i < r.patternLen-1; i++ {
		highestPow = (highestPow * 256) % r.prime
	}

	for i := 0; i <= len(text)-r.patternLen; i++ {
		if textHash == r.patternHash {
			match := true
			for j := 0; j < r.patternLen; j++ {
				if text[i+j] != r.pattern[j] {
					match = false
					break
				}
			}
			if match {
				return i
			}
		}

		if i < len(text)-r.patternLen {
			textHash = (256*(textHash - int(text[i])*highestPow) + int(text[i+r.patternLen])) % r.prime
			if textHash < 0 {
				textHash += r.prime
			}
		}
	}
	return -1
}

func main() {
	text := "ababc"
	pattern := "abc"
	rk := NewRabinKarp(pattern)
	index := rk.Search(text)
	if index != -1 {
		fmt.Printf("Pattern found at index %d\n", index)
	} else {
		fmt.Println("Pattern not found")
	}
}

r.patternHash = r.hash(pattern, r.patternLen)

Calculate hash of the pattern once for comparison

textHash := r.hash(text, r.patternLen)

Calculate initial hash of the first window in text

for i := 0; i <= len(text)-r.patternLen; i++ {

Slide window over text to check each substring

if textHash == r.patternHash {

If hashes match, verify characters to avoid false positives

textHash = (256*(textHash - int(text[i])*highestPow) + int(text[i+r.patternLen])) % r.prime

Recalculate hash for next window using rolling hash formula

if textHash < 0 { textHash += r.prime }

Adjust hash to be positive if modulo gave negative

Output

Pattern found at index 2

Complexity Analysis

Time: O(n + m) because we compute initial hashes in O(m) and slide over text of length n with O(1) hash updates

Space: O(m) for storing the pattern and its hash

vs Alternative: Compared to naive O(n*m) substring checks, Rabin Karp uses hashing to reduce average time to O(n + m)

Edge Cases

Empty text

Returns -1 immediately since no match is possible

DSA Go

if len(text) < r.patternLen { return -1 }

Pattern longer than text

Returns -1 immediately as pattern cannot fit

DSA Go

if len(text) < r.patternLen { return -1 }

Multiple occurrences of pattern

Returns the first match index found

DSA Go

return i when match is confirmed

When to Use This Pattern

When you need to find a substring quickly and want to avoid checking every character repeatedly, use Rabin Karp because it uses hashing to speed up comparisons.

Common Mistakes

Mistake: Not verifying characters after hash match, causing false positives
Fix: Always compare characters after hash matches to confirm actual match

Mistake: Not handling negative hash values after modulo operation
Fix: Add prime to hash if it becomes negative to keep it positive

Summary

It finds a pattern in text by comparing hash values instead of characters directly.

Use it when you want faster substring search than checking every character.

The key insight is using a rolling hash to quickly update and compare substring hashes.

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