Rabin Karp String Matching in DSA Javascript - Build from Scratch

Rabin Karp String Matching

📖 Scenario: You are building a simple search tool that finds a small word inside a larger text quickly. This is useful in text editors or search engines.

🎯 Goal: Build a program that uses the Rabin Karp algorithm to find all starting positions of a pattern inside a given text.

📋 What You'll Learn

Create variables for the text and pattern strings

Set up variables for the pattern length, text length, and a prime number for hashing

Implement the Rabin Karp algorithm to find all occurrences of the pattern in the text

Print the list of starting indices where the pattern is found

💡 Why This Matters

🌍 Real World

Rabin Karp is used in text editors and search engines to quickly find words or phrases inside large documents.

💼 Career

Understanding string matching algorithms like Rabin Karp is important for software developers working on search features, data processing, and text analysis.

1

Create the text and pattern strings

Create a variable called text and set it to the string "abracadabra". Create another variable called pattern and set it to the string "abra".

DSA Javascript

# Your code here

Hint

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

2

Set up helper variables for lengths and prime number

Create a variable called m and set it to the length of pattern. Create a variable called n and set it to the length of text. Create a variable called prime and set it to 101.

DSA Javascript

const text = "abracadabra";
const pattern = "abra";
# Your code here

Hint

Use pattern.length and text.length to get lengths. Use const for all variables.

3

Implement the Rabin Karp algorithm core logic

Create a function called rabinKarpSearch that takes text, pattern, prime, m, and n as parameters. Inside it, implement the Rabin Karp algorithm to find all starting indices where pattern occurs in text. Return an array called result containing these indices.

DSA Javascript

const text = "abracadabra";
const pattern = "abra";
const m = pattern.length;
const n = text.length;
const prime = 101;

# Your code here

Hint

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

4

Print the result of the Rabin Karp search

Call the function rabinKarpSearch with text, pattern, prime, m, and n. Store the result in a variable called positions. Then print positions.

DSA Javascript

const text = "abracadabra";
const pattern = "abra";
const m = pattern.length;
const n = text.length;
const prime = 101;

function rabinKarpSearch(text, pattern, prime, m, n) {
    const result = [];
    const d = 256; // number of characters in input alphabet
    let p = 0; // hash value for pattern
    let t = 0; // hash value for text
    let h = 1;

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

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

    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)) % prime;
            if (t < 0) {
                t = t + prime;
            }
        }
    }
    return result;
}

# Your code here

Hint

Call the function with the correct arguments and print the returned array.

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