Rabin Karp String Matching in DSA Javascript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to calculate the initial hash of the pattern.

DSA Javascript

let patternHash = 0;
for (let i = 0; i < pattern.length; i++) {
  patternHash = (patternHash * base + pattern.charCodeAt(i)) [1] mod;
}

Drag options to blanks, or click blank then click option'

A+

B%

C-

D*

Attempts:

3 left

💡 Hint

Common Mistakes

Using addition instead of modulo causes incorrect hash values.

Forgetting modulo leads to very large numbers and errors.

The modulo operator (%) is used to keep the hash value within a fixed range to avoid overflow.

2fill in blank

medium

Complete the code to update the rolling hash when sliding the window.

DSA Javascript

textHash = (textHash - text.charCodeAt(i) * power) [1] mod;
textHash = (textHash * base + text.charCodeAt(i + pattern.length)) % mod;

Drag options to blanks, or click blank then click option'

A+

B*

C-

D%

Attempts:

3 left

💡 Hint

Common Mistakes

Not using modulo after subtraction causes negative hash values.

Using addition instead of modulo leads to wrong hash updates.

Modulo is used to keep the hash value within range after subtraction.

3fill in blank

hard

Fix the error in the code that compares the substring with the pattern after hash match.

DSA Javascript

if (textHash === patternHash) {
  if (text.substr(i, pattern.length) [1] pattern) {
    result.push(i);
  }
}

Drag options to blanks, or click blank then click option'

A!==

B==

C===

D!=

Attempts:

3 left

💡 Hint

Common Mistakes

Using == can cause unexpected results due to type coercion.

Using != or !== is incorrect for equality check.

Use strict equality (===) to correctly compare strings in JavaScript.

4fill in blank

hard

Fill both blanks to correctly calculate the power used in rolling hash.

DSA Javascript

let power = 1;
for (let i = 0; i < pattern.length - 1; i++) {
  power = (power [1] base) [2] mod;
}

Drag options to blanks, or click blank then click option'

A*

B+

C%

D-

Attempts:

3 left

💡 Hint

Common Mistakes

Using addition instead of multiplication changes the power calculation.

Forgetting modulo causes large numbers and errors.

Multiply power by base and then take modulo to keep the number within range.

5fill in blank

hard

Fill all three blanks to complete the Rabin Karp search function.

DSA Javascript

function rabinKarp(text, pattern) {
  const base = 256;
  const mod = 101;
  let patternHash = 0, textHash = 0, power = 1;
  let result = [];

  for (let i = 0; i < pattern.length - 1; i++) {
    power = (power [1] base) [2] mod;
  }

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

  for (let i = 0; i <= text.length - pattern.length; i++) {
    if (textHash === patternHash) {
      if (text.substr(i, pattern.length) [3] pattern) {
        result.push(i);
      }
    }
    if (i < text.length - pattern.length) {
      textHash = (textHash - text.charCodeAt(i) * power) % mod;
      textHash = (textHash * base + text.charCodeAt(i + pattern.length)) % mod;
      if (textHash < 0) textHash += mod;
    }
  }
  return result;
}

Drag options to blanks, or click blank then click option'

A*

B+

C%

D===

Attempts:

3 left

💡 Hint

Common Mistakes

Using loose equality (==) instead of strict equality (===).

Forgetting modulo after multiplication.

Not handling negative hash values after subtraction.

Multiply power by base and modulo; use strict equality (===) to compare strings.

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