Rabin Karp String Matching in DSA Typescript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

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

DSA Typescript

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

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

Atext.length

Bpattern.length

Cprime

Dbase

Attempts:

3 left

💡 Hint

Common Mistakes

Using pattern.length or text.length as modulus causes incorrect hash calculations.

Not using modulus leads to integer overflow.

The modulus with a prime number keeps the hash values manageable and reduces collisions.

2fill in blank

medium

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

DSA Typescript

textHash = (textHash - text.charCodeAt(i - 1) * [1]) * base + text.charCodeAt(i + pattern.length - 1);
textHash %= prime;
if (textHash < 0) textHash += prime;

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

Aprime

Bbase ** (pattern.length - 1)

Cpattern.length

Dbase

Attempts:

3 left

💡 Hint

Common Mistakes

Subtracting old char code multiplied by base instead of base^(pattern.length - 1).

Not adjusting negative hash values after modulus.

We subtract the old character's weighted value using base raised to (pattern.length - 1).

3fill in blank

hard

Fix the error in the hash comparison condition to check for a match.

DSA Typescript

if (patternHash === [1]) {
  // Verify characters one by one
}

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

Abase

BpatternHash

Ctext.charCodeAt(i)

DtextHash

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing patternHash with itself always returns true.

Comparing with base or a single character code is wrong.

We compare the pattern's hash with the current text window's hash to detect potential matches.

4fill in blank

hard

Fill both blanks to complete the loop that slides over the text and updates the hash.

DSA Typescript

for (let i = 1; i <= text.length - pattern.length; i++) {
  textHash = (textHash - text.charCodeAt(i - 1) * [1]) * base + text.charCodeAt(i + pattern.length - 1);
  textHash %= [2];
  if (textHash < 0) textHash += [2];
  // Check for match
}

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

AbasePow

Bpattern.length

Cprime

Dbase

Attempts:

3 left

💡 Hint

Common Mistakes

Using base or pattern.length as modulus causes wrong hash values.

Not adding prime when hash is negative leads to errors.

We subtract the old char weighted by basePow and take modulus with prime to keep hash in range.

5fill in blank

hard

Fill all three blanks to complete the function that returns all starting indices of pattern matches in text.

DSA Typescript

function rabinKarp(text: string, pattern: string): number[] {
  const result: number[] = [];
  const base = 256;
  const prime = 101;
  let patternHash = 0, textHash = 0, basePow = 1;

  for (let i = 0; i < pattern.length - 1; i++) {
    basePow = (basePow * base) % prime;
  }

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

  for (let i = 0; i <= text.length - pattern.length; i++) {
    if (patternHash === textHash) {
      let match = true;
      for (let j = 0; j < pattern.length; j++) {
        if (text[i + j] !== pattern[j]) {
          match = false;
          break;
        }
      }
      if (match) result.push([1]);
    }
    if (i < text.length - pattern.length) {
      textHash = (textHash - text.charCodeAt(i) * [2]) * base + text.charCodeAt(i + pattern.length);
      textHash %= [3];
      if (textHash < 0) textHash += [3];
    }
  }
  return result;
}

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

Ai

BbasePow

Cprime

Dpattern.length

Attempts:

3 left

💡 Hint

Common Mistakes

Pushing pattern.length or base instead of current index.

Using base or pattern.length as modulus causes wrong hash updates.

We push the current index i when a match is found, subtract old char weighted by basePow, and use prime as modulus.

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