Rabin Karp String Matching in DSA Go - Time & Space Complexity

Time Complexity: Rabin Karp String Matching

O(n + m)

Understanding Time Complexity

We want to understand how the Rabin Karp algorithm's running time changes as the text and pattern sizes grow.

Specifically, how many steps does it take to find a pattern in a text?

Scenario Under Consideration

Analyze the time complexity of the following Rabin Karp code snippet.

func rabinKarp(text, pattern string) int {
    n, m := len(text), len(pattern)
    if m > n {
        return -1
    }
    const base, mod = 256, 101
    var patternHash, textHash, h int = 0, 0, 1

    for i := 0; i < m-1; i++ {
        h = (h * base) % mod
    }

    for i := 0; i < m; i++ {
        patternHash = (base*patternHash + int(pattern[i])) % mod
        textHash = (base*textHash + int(text[i])) % mod
    }

    for i := 0; i < n-m+1; i++ {
        if patternHash == textHash {
            match := true
            for j := 0; j < m; j++ {
                if text[i+j] != pattern[j] {
                    match = false
                    break
                }
            }
            if match {
                return i
            }
        }
        if i < n-m {
            textHash = (base*(textHash-int(text[i])*h) + int(text[i+m])) % mod
            if textHash < 0 {
                textHash += mod
            }
        }
    }
    return -1
}
    

This code searches for a pattern in a text using rolling hash to speed up comparisons.

Identify Repeating Operations

Look at the loops and repeated steps:

• Primary operation: The outer loop sliding over the text (runs about n-m+1 times).
• Secondary operation: The inner loop checking characters when hashes match (runs up to m times, but only on hash matches).
• Hash computations: Calculated once for pattern and initial text window, then updated in constant time each slide.

How Execution Grows With Input

As the text length (n) grows, the algorithm checks more windows. The pattern length (m) affects how many characters are compared when hashes match.

Input Size (n)	Approx. Operations
10	About 10 hash checks, few character checks
100	About 100 hash checks, some character checks on matches
1000	About 1000 hash checks, occasional character checks

Pattern length m affects character checks only when hashes match, which is rare on average, so most work is hash updates sliding over n.

Final Time Complexity

Time Complexity: O(n + m)

This means the algorithm usually checks each character in the text once plus the pattern length, making it efficient for large inputs.

Common Mistake

[X] Wrong: "Rabin Karp always runs in O(n) time because it never compares characters directly."

[OK] Correct: Sometimes hashes collide, causing character-by-character checks that can take up to O(m) time per match, making worst case O(n*m).

Interview Connect

Understanding Rabin Karp's time complexity shows you how hashing can speed up searching and when it might slow down, a useful skill for string problems.

Self-Check

"What if we used a larger prime modulus to reduce hash collisions? How would that affect the time complexity?"

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