Rabin Karp String Matching in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Rabin Karp hash calculation

What is the output of the following JavaScript code that calculates the initial hash for the pattern 'abc' using a simple rolling hash?

DSA Javascript

const pattern = 'abc';
const base = 256;
const mod = 101;
let hash = 0;
for (let i = 0; i < pattern.length; i++) {
  hash = (hash * base + pattern.charCodeAt(i)) % mod;
}
console.log(hash);

A 6

B 45

C 12

D 90

💡 Hint

Calculate hash step by step: hash = (hash * base + charCode) % mod for each character.

The hash is computed as ((('a' * 256 + 'b') * 256) + 'c') mod 101. Calculating stepwise gives 90.

❓ Predict Output

intermediate

Rabin Karp pattern search output

What will be printed by the following code that searches for pattern 'test' in text 'this is a test text' using Rabin Karp?

DSA Javascript

function rabinKarp(text, pattern) {
  const base = 256;
  const mod = 101;
  const m = pattern.length;
  const n = text.length;
  let pHash = 0, tHash = 0, h = 1;

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

  for (let i = 0; i < m; i++) {
    pHash = (pHash * base + pattern.charCodeAt(i)) % mod;
    tHash = (tHash * base + text.charCodeAt(i)) % mod;
  }

  for (let i = 0; i <= n - m; i++) {
    if (pHash === tHash) {
      let match = true;
      for (let j = 0; j < m; j++) {
        if (text[i + j] !== pattern[j]) {
          match = false;
          break;
        }
      }
      if (match) console.log(i);
    }
    if (i < n - m) {
      tHash = (base * (tHash - text.charCodeAt(i) * h) + text.charCodeAt(i + m)) % mod;
      if (tHash < 0) tHash += mod;
    }
  }
}
rabinKarp('this is a test text', 'test');

A 8

B 10

C 15

D 5

💡 Hint

Check the index where 'test' starts in the text.

The substring 'test' starts at index 10 in the text 'this is a test text'.

🧠 Conceptual

advanced

Why use modulo in Rabin Karp hashing?

Why does the Rabin Karp algorithm use modulo operation when calculating the rolling hash?

A To keep hash values within a fixed range and avoid integer overflow

B To make the hash values unique for every substring

C To speed up the string comparison step

D To convert characters to numbers

💡 Hint

Think about what happens if numbers get too big in calculations.

Modulo keeps hash values within a manageable range and prevents overflow during calculations.

🔧 Debug

advanced

Identify the bug in rolling hash update

What is the bug in the following rolling hash update code snippet used in Rabin Karp?

DSA Javascript

tHash = (base * (tHash - text.charCodeAt(i) * h) + text.charCodeAt(i + m)) % mod;

A It should subtract text.charCodeAt(i + m) instead of adding

B It uses wrong base value for multiplication

C It does not add mod if tHash becomes negative

D It should multiply by h instead of base

💡 Hint

Check what happens if the subtraction makes tHash negative.

If tHash becomes negative after subtraction, it must be adjusted by adding mod to keep it positive.

🚀 Application

expert

Number of hash collisions in Rabin Karp

Given a text of length 1000 and a pattern of length 5, using Rabin Karp with base=256 and mod=101, what is the maximum number of hash collisions that can occur during the search?

A 995

B 1000

C 101

D 5

💡 Hint

Number of substrings checked is n - m + 1; collisions can happen at each substring except the first.

There are 996 substrings of length 5 in text length 1000. Maximum collisions can happen at all except the first hash calculation, so 995.

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