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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Rabin Karp hash calculation

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

DSA Typescript

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

A 90

B 6

C 97

D 99

💡 Hint

Calculate hash step by step using modulo arithmetic.

The hash is calculated as (((0 * 256 + 'a') % 101) * 256 + 'b') % 101, then multiplied by 256 and added 'c' modulo 101. The final value is 90.

🧠 Conceptual

intermediate

Understanding the rolling hash update in Rabin Karp

In Rabin Karp algorithm, when sliding the window over the text, how is the rolling hash updated to remove the leftmost character and add the new rightmost character?

A Subtract leftmost character's weighted value, multiply by base, add new character's code, then take modulo prime

B Subtract the leftmost character's weighted value, multiply by base, add new character, then take modulo prime

C Multiply current hash by base, add new character's code, then subtract leftmost character's code, take modulo prime

D Add new character's code, subtract leftmost character's code, multiply by base, then take modulo prime

💡 Hint

Think about removing the old character's contribution before adding the new one.

The rolling hash removes the leftmost character's weighted value (left_char * base^(pattern_length-1)), multiplies the remaining hash by base, adds the new character's code, and then takes modulo prime.

🔧 Debug

advanced

Identify the error in this Rabin Karp hash update code

What error will the following TypeScript code produce when updating the rolling hash in Rabin Karp?

DSA Typescript

const base = 256;
const prime = 101;
const patternLength = 3;
let highestBasePower = Math.pow(base, patternLength - 1) % prime;
let oldHash = 94;
const leftCharCode = 'a'.charCodeAt(0);
const newCharCode = 'd'.charCodeAt(0);
let newHash = (oldHash - leftCharCode * highestBasePower) * base + newCharCode % prime;
console.log(newHash);

A Prints NaN

B Prints a positive number but incorrect hash

C Prints the correct updated hash

D Prints a negative number

💡 Hint

Check operator precedence and modulo placement.

The modulo operator is applied only to newCharCode, not the entire expression, causing the subtraction result to be negative and no modulo applied to the whole expression, leading to a negative hash.

🚀 Application

advanced

Number of pattern matches found by Rabin Karp

Given the text 'abracadabra' and pattern 'abra', how many matches will the Rabin Karp algorithm find?

A 1

B 2

C 3

D 4

💡 Hint

Look for all occurrences of 'abra' in the text.

The pattern 'abra' appears twice in 'abracadabra': at the start (index 0) and near the end (index 7).

🧠 Conceptual

expert

Why does Rabin Karp use a prime number in hashing?

Why is a prime number used as the modulo base in the Rabin Karp rolling hash algorithm?

A To make the hash values smaller than the pattern length

B Because prime numbers are easier to compute with in modular arithmetic

C To reduce the chance of hash collisions by distributing hash values uniformly

D To ensure the hash values are always positive integers

💡 Hint

Think about how modulo with prime affects distribution of values.

Using a prime number as modulo helps spread hash values more uniformly, reducing collisions and improving algorithm efficiency.

Practice

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

easy

A. Use hashing to find pattern matches efficiently

B. Use recursion to match patterns

C. Sort the text and pattern before matching

D. Use brute force to check every substring

Solution

1. Step 1: Understand the algorithm's approach

   The Rabin Karp algorithm uses a hash function to convert strings into numbers for quick comparison.

2. Step 2: Identify the benefit of hashing

   Hashing allows checking if substrings match the pattern by comparing hash values instead of characters directly.

3. Final Answer:

   Use hashing to find pattern matches efficiently -> Option A

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 checking

2. Which of the following is the correct way to compute the initial hash of a string s of length m using a base d and a prime modulus q in TypeScript?

easy

A. let hash = 0; for(let i=0; i

B. let hash = 1; for(let i=0; i

C. let hash = 0; for(let i=0; i

D. let hash = 0; for(let i=0; i

Solution

1. Step 1: Understand the rolling hash formula

   The hash is computed as hash = (hash * d + current_char) mod q for each character.

2. Step 2: Match the code with the formula

   let hash = 0; for(let i=0; i

3. Final Answer:

   let hash = 0; for(let i=0; i -> Option A

4. Quick Check:

   Rolling hash = (prev_hash * d + char) % q [OK]

Hint: Hash = (prev_hash * base + char) mod prime [OK]

Common Mistakes:

• Mixing up base and modulus in calculation
• Starting hash from 1 instead of 0
• Incorrect order of operations in formula

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

const text = "ababcabc";
const pattern = "abc";
const d = 256;
const q = 101;

function rabinKarp(text: string, pattern: string): number[] {
  const m = pattern.length;
  const n = text.length;
  let p = 0, t = 0, h = 1;
  const result: number[] = [];

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

  for (let i = 0; i < m; i++) {
    p = (d * p + pattern.charCodeAt(i)) % q;
    t = (d * t + text.charCodeAt(i)) % q;
  }

  for (let i = 0; i <= n - m; i++) {
    if (p === t) {
      let match = true;
      for (let j = 0; j < m; j++) {
        if (text[i + j] !== pattern[j]) {
          match = false;
          break;
        }
      }
      if (match) result.push(i);
    }
    if (i < n - m) {
      t = (d * (t - text.charCodeAt(i) * h) + text.charCodeAt(i + m)) % q;
      if (t < 0) t += q;
    }
  }
  return result;
}

console.log(rabinKarp(text, pattern));

medium

A. [2, 4, 6]

B. [0, 3, 5]

C. [1, 4]

D. [2, 5]

Solution

1. Step 1: Identify pattern occurrences in text

   The pattern "abc" appears starting at index 2 ("ababcabc") and index 5.

2. Step 2: Verify code logic for matching indices

   The code correctly finds these two positions and returns [2, 5].

3. Final Answer:

   [2, 5] -> Option D

4. Quick Check:

   Pattern found at indices 2 and 5 [OK]

Hint: Check substring start indices where pattern matches [OK]

Common Mistakes:

• Including index 0 which is partial match
• Confusing overlapping matches
• Forgetting to adjust negative hash values

4. The following Rabin Karp implementation has a bug causing incorrect matches. What is the error?

function rabinKarpBug(text: string, pattern: string): number[] {
  const m = pattern.length;
  const n = text.length;
  const d = 256;
  const q = 101;
  let p = 0, t = 0, h = 1;
  const result: number[] = [];

  for (let i = 0; i < m; i++) h = (h * d) % q;

  for (let i = 0; i < m; i++) {
    p = (d * p + pattern.charCodeAt(i)) % q;
    t = (d * t + text.charCodeAt(i)) % q;
  }

  for (let i = 0; i <= n - m; i++) {
    if (p === t) {
      let match = true;
      for (let j = 0; j < m; j++) {
        if (text[i + j] !== pattern[j]) {
          match = false;
          break;
        }
      }
      if (match) result.push(i);
    }
    if (i < n - m) {
      t = (d * (t - text.charCodeAt(i) * h) + text.charCodeAt(i + m)) % q;
      if (t < 0) t += q;
    }
  }
  return result;
}

medium

A. The hash update formula inside the loop is missing modulo operation

B. The initial value of h is computed incorrectly; it should be for (i = 0; i < m-1; i++)

C. The pattern hash p is not computed correctly

D. The loop for checking matches uses wrong indices

Solution

1. Step 1: Check computation of h

   Variable h should be (d^(m-1)) % q, but loop runs m times, making h too large.

2. Step 2: Understand impact on rolling hash

   Incorrect h causes wrong subtraction in rolling hash, leading to incorrect matches.

3. Final Answer:

   The initial value of h is computed incorrectly; it should be for (i = 0; i < m-1; i++) -> Option B

4. Quick Check:

   h loop runs m-1 times, not m [OK]

Hint: Compute h with loop to m-1, not m [OK]

Common Mistakes:

• Calculating h with wrong loop range
• Forgetting modulo in hash updates
• Misindexing pattern or text in loops

5. You want to use Rabin Karp to find all occurrences of pattern "aaa" in text "aaaaaa". What is the output of the algorithm and why is it important to verify matches after hash comparison?

hard

A. [0, 1, 2, 3, 4], because every substring is checked without hash

B. [0, 3], because only non-overlapping matches are counted

C. [0, 1, 2, 3], because overlapping matches exist and hash collisions can occur

D. [0], because Rabin Karp only finds first match

Solution

1. Step 1: Identify all pattern occurrences in text

   The pattern "aaa" appears starting at indices 0, 1, 2, and 3 in "aaaaaa" due to overlapping.

2. Step 2: Explain importance of verifying matches after hash

   Hash collisions can cause false positives, so character-by-character check confirms actual matches.

3. Final Answer:

   [0, 1, 2, 3], because overlapping matches exist and hash collisions can occur -> Option C

4. Quick Check:

   Overlapping matches + verify after hash = [0,1,2,3] [OK]

Hint: Check overlapping matches and confirm after hashing [OK]

Common Mistakes:

• Ignoring overlapping matches
• Assuming hash guarantees no false positives
• Counting only first or non-overlapping matches