Rabin Karp String Matching in DSA Typescript - Build from Scratch

Rabin Karp String Matching

📖 Scenario: You are building a simple search tool that finds if a small word (pattern) exists inside a larger text. This is like looking for a word in a book quickly.

🎯 Goal: Build a program that uses the Rabin Karp algorithm to check if a pattern string exists in a text string by comparing hash values.

📋 What You'll Learn

Create variables for the text and pattern strings

Create a variable for the prime number used in hashing

Implement the Rabin Karp algorithm to find the pattern in the text

Print the starting index of the pattern in the text or -1 if not found

💡 Why This Matters

🌍 Real World

Searching for words or phrases quickly in large documents, like searching in text editors or databases.

💼 Career

Understanding efficient string search algorithms is important for software developers working on text processing, search engines, and data analysis.

1

Create the text and pattern strings

Create a variable called text and set it to the string "hello world". Create another variable called pattern and set it to the string "world".

DSA Typescript

// Your code here

Hint

Use const to create variables for the text and pattern strings exactly as given.

2

Set the prime number for hashing

Create a variable called prime and set it to the number 101. This will be used as the prime number in the hashing function.

DSA Typescript

const text = "hello world";
const pattern = "world";
// Your code here

Hint

Use const prime = 101; to set the prime number.

3

Implement the Rabin Karp algorithm

Write a function called rabinKarpSearch that takes text, pattern, and prime as parameters. Inside, implement the Rabin Karp algorithm to find the starting index of pattern in text. Return the index if found, otherwise return -1. Use variables textLength and patternLength for lengths, and calculate initial hash values for pattern and text windows. Use a loop with i and j as indices. Use a variable h for the highest power of base 256 modulo prime. Use base 256 for characters. Follow the Rabin Karp steps carefully.

DSA Typescript

const text = "hello world";
const pattern = "world";
const prime = 101;
// Your code here

Hint

Follow the Rabin Karp algorithm steps: calculate initial hashes, slide the window, compare hashes, and check characters if hashes match.

4

Print the result of the search

Call the function rabinKarpSearch with text, pattern, and prime. Print the returned index using console.log.

DSA Typescript

const text = "hello world";
const pattern = "world";
const prime = 101;

function rabinKarpSearch(text: string, pattern: string, prime: number): number {
    const textLength = text.length;
    const patternLength = pattern.length;
    if (patternLength > textLength) return -1;

    let patternHash = 0;
    let textHash = 0;
    let h = 1;
    const base = 256;

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

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

    for (let i = 0; i <= textLength - patternLength; i++) {
        if (patternHash === textHash) {
            let match = true;
            for (let j = 0; j < patternLength; j++) {
                if (text[i + j] !== pattern[j]) {
                    match = false;
                    break;
                }
            }
            if (match) return i;
        }
        if (i < textLength - patternLength) {
            textHash = (base * (textHash - text.charCodeAt(i) * h) + text.charCodeAt(i + patternLength)) % prime;
            if (textHash < 0) textHash += prime;
        }
    }
    return -1;
}

// Your code here

Hint

Call rabinKarpSearch(text, pattern, prime) and print the result with console.log.

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