Rabin Karp String Matching in DSA Javascript - 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.

function rabinKarp(text, pattern) {
  const n = text.length;
  const m = pattern.length;
  const base = 256;
  const prime = 101;
  let patternHash = 0, textHash = 0, h = 1;

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

  for (let i = 0; i < m; i++) {
    patternHash = (base * patternHash + pattern.charCodeAt(i)) % prime;
    textHash = (base * textHash + text.charCodeAt(i)) % prime;
  }

  for (let i = 0; i <= n - m; i++) {
    if (patternHash === textHash) {
      let match = true;
      for (let 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 - text.charCodeAt(i) * h) + text.charCodeAt(i + m)) % prime;
      if (textHash < 0) textHash += prime;
    }
  }
  return -1;
}
    

This code searches for a pattern inside a text using hashing to speed up comparisons.

Identify Repeating Operations

Look at the loops and repeated checks:

• Primary operation: The outer loop sliding over the text (runs about n - m + 1 times).
• Secondary operation: The inner loop comparing characters when hashes match (runs up to m times, but only on hash matches).

How Execution Grows With Input

As the text size (n) grows, the outer loop runs roughly n times. The pattern size (m) affects the inner character checks.

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

Pattern matching checks happen only when hashes match, so most of the time the algorithm quickly skips ahead.

Final Time Complexity

Time Complexity: O(n + m) on average, O(nm) in the worst case due to hash collisions.

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

Common Mistake

[X] Wrong: "Rabin Karp always compares every character in the text to the pattern."

[OK] Correct: Actually, it uses hash values to skip many unnecessary character comparisons, so it rarely checks every character directly.

Interview Connect

Understanding Rabin Karp's time complexity shows you how hashing helps speed up searching tasks, a useful skill for many coding problems.

Self-Check

"What if the hash function caused many collisions? How would that affect the time complexity?"

Practice

1. What is the main idea behind the Rabin Karp String Matching algorithm?

easy

A. Sort the text and pattern before matching

B. Use recursion to search for the pattern

C. Use hashing to find pattern matches efficiently

D. Use brute force to compare every substring

Solution

1. Step 1: Understand Rabin Karp's approach

   The algorithm uses a hash function to convert the pattern and substrings of the text into numbers.

2. Step 2: Use hashing for efficient matching

   By comparing hash values instead of characters, it quickly finds potential matches and then verifies them.

3. Final Answer:

   Use hashing to find pattern matches efficiently -> Option C

4. Quick Check:

   Rabin Karp = hashing for matching [OK]

Hint: Remember: Rabin Karp uses hashing to speed up matching [OK]

Common Mistakes:

• Thinking it uses recursion
• Assuming it sorts strings before matching
• Confusing it with brute force method

2. Which of the following is the correct way to compute the initial hash for a substring in Rabin Karp (assuming base = 256 and prime = 101)?

easy

A. hash = (charCode + prime) % base

B. hash = (hash * base + charCode) % prime

C. hash = (charCode * base) % prime

D. hash = (hash + base * charCode) % prime

Solution

1. Step 1: Understand hash calculation formula

   The rolling hash is computed by multiplying the current hash by base and adding the new character code, then taking modulo prime.

2. Step 2: Match formula with options

   hash = (hash * base + charCode) % prime matches the formula: hash = (hash * base + charCode) % prime.

3. Final Answer:

   hash = (hash * base + charCode) % prime -> Option B

4. Quick Check:

   Rolling hash formula = hash = (hash * base + charCode) % prime [OK]

Hint: Rolling hash multiplies old hash by base, adds char, mod prime [OK]

Common Mistakes:

• Adding base multiplied by charCode instead of multiplying hash
• Mixing up modulo operations
• Using wrong order of operations

3. What will be the output of the following code snippet using Rabin Karp to find pattern 'abc' in text 'ababc'?

const text = 'ababc';
const pattern = 'abc';
// Assume base=256, prime=101
// Simplified hash function and matching logic
function rabinKarp(text, pattern) {
  const m = pattern.length;
  const n = text.length;
  for (let i = 0; i <= n - m; i++) {
    if (text.substring(i, i + m) === pattern) {
      return i;
    }
  }
  return -1;
}
console.log(rabinKarp(text, pattern));

medium

A. 2

B. 1

C. -1

D. 3

Solution

1. Step 1: Check substring matches

   Check substrings of length 3 in 'ababc': 'aba'(index 0), 'bab'(1), 'abc'(2).

2. Step 2: Identify matching index

   'abc' matches at index 2, so function returns 2.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Pattern found at index 2 [OK]

Hint: Check substrings of pattern length for exact match [OK]

Common Mistakes:

• Returning first partial match index
• Off-by-one errors in loop
• Confusing substring indices

4. Identify the bug in this Rabin Karp implementation snippet:

function rabinKarp(text, pattern) {
  const base = 256;
  const prime = 101;
  let patternHash = 0, textHash = 0;
  const m = pattern.length;
  const n = text.length;
  let h = 1;

  for (let i = 0; i < m; i++) {
    h = (h * base) % prime;
  }

  for (let i = 0; i < m; i++) {
    patternHash = (base * patternHash + pattern.charCodeAt(i)) % prime;
    textHash = (base * textHash + text.charCodeAt(i)) % prime;
  }

  for (let i = 0; i <= n - m; i++) {
    if (patternHash === textHash) {
      if (text.substring(i, i + m) === pattern) {
        return i;
      }
    }
    if (i < n - m) {
      textHash = (base * (textHash - text.charCodeAt(i) * h) + text.charCodeAt(i + m)) % prime;
      if (textHash < 0) textHash += prime;
    }
  }
  return -1;
}

medium

A. Not updating patternHash inside the loop

B. Missing check for negative textHash after update

C. Using substring instead of charAt for comparison

D. Incorrect calculation of h in the first loop

Solution

1. Step 1: Examine the h calculation

   The variable h should be base^(m-1) % prime to multiply the outgoing character's contribution.

2. Step 2: Identify the loop error

   The loop runs from i=0 to i

3. Final Answer:

   Incorrect calculation of h in the first loop -> Option D

4. Quick Check:

   h = base^(m-1) % prime requires loop m-1 times [OK]

Hint: Check h calculation loop carefully for off-by-one errors [OK]

Common Mistakes:

• Forgetting to add prime if textHash becomes negative
• Incorrect loop range for h calculation
• Not verifying substring match after hash match

5. Given a large text and multiple patterns, which modification to the Rabin Karp algorithm helps efficiently find all patterns in the text?

hard

A. Precompute hashes of all patterns and use a hash set for quick lookup

B. Sort all patterns and use binary search on text substrings

C. Use a single hash function and check each pattern separately

D. Use recursion to match patterns one by one

Solution

1. Step 1: Understand multiple pattern matching challenge

   Checking each pattern separately is slow for many patterns.

2. Step 2: Use hashing for all patterns

   Precompute hashes of all patterns and store in a hash set for O(1) lookup during text scanning.

3. Step 3: Efficiently find all matches

   When scanning text substrings, compute hash and check if it exists in the pattern hash set to find matches quickly.

4. Final Answer:

   Precompute hashes of all patterns and use a hash set for quick lookup -> Option A

5. Quick Check:

   Multiple patterns = precompute hashes + hash set [OK]

Hint: Precompute pattern hashes and use hash set for fast matching [OK]

Common Mistakes:

• Checking each pattern separately causing slow performance
• Sorting patterns instead of hashing
• Using recursion unnecessarily