Rabin Karp String Matching in DSA Javascript

Mental Model

We use a number to represent a string and slide over the text to find matches quickly by comparing these numbers instead of characters.

Analogy: Imagine checking if a small painting is inside a big mural by comparing the color codes of small sections instead of looking at every detail each time.

Text:  T -> h -> i -> s ->   -> i -> s ->   -> a ->   -> t -> e -> x -> t -> null
Pattern:  a ->   -> t -> null
Hash: pattern_hash = 123, current_text_hash = 456
Window slides over text characters

Dry Run Walkthrough

Input: text: 'ababc', pattern: 'abc'

Goal: Find the starting index where 'abc' appears in 'ababc' using Rabin Karp hashing

Step 1: Calculate hash of pattern 'abc' and first window 'aba' in text

pattern_hash=hash('abc')=some_number, window_hash=hash('aba')=some_number
Text window: [a] -> b -> a -> b -> c -> null

Why: We need initial hashes to compare pattern with the first part of text

Step 2: Compare pattern_hash and window_hash; they differ, so slide window by one

Text window: a -> [b] -> a -> b -> c -> null
window_hash updated to hash('bab')

Why: Hashes differ, so no match; move window to next substring

Step 3: Compare pattern_hash and window_hash; they differ, slide window again

Text window: a -> b -> [a] -> b -> c -> null
window_hash updated to hash('abc')

Why: Still no match; slide window to next substring

Step 4: Compare pattern_hash and window_hash; they match, verify characters

Text window: a -> b -> a -> [b] -> c -> null
Characters match 'abc' exactly

Why: Hashes match, so check characters to confirm pattern found

Result:

Final state: pattern found at index 2 in text
Answer: 2

Annotated Code

DSA Javascript

class RabinKarp {
  constructor() {
    this.prime = 101; // prime number for modulo
    this.base = 256; // number of characters in input alphabet
  }

  // Compute initial hash for a string of length m
  computeHash(str, m) {
    let hash = 0;
    for (let i = 0; i < m; i++) {
      hash = (hash * this.base + str.charCodeAt(i)) % this.prime;
    }
    return hash;
  }

  // Recalculate hash by removing left char and adding right char
  recalcHash(oldHash, leftChar, rightChar, highestBase) {
    let newHash = oldHash - leftChar.charCodeAt(0) * highestBase;
    newHash = (newHash * this.base + rightChar.charCodeAt(0)) % this.prime;
    if (newHash < 0) newHash += this.prime;
    return newHash;
  }

  search(text, pattern) {
    const n = text.length;
    const m = pattern.length;
    if (m > n) return -1;

    const highestBase = Math.pow(this.base, m - 1) % this.prime;
    const patternHash = this.computeHash(pattern, m);
    let windowHash = this.computeHash(text, m);

    for (let i = 0; i <= n - m; i++) {
      if (patternHash === windowHash) {
        // Verify characters one by one
        let match = true;
        for (let j = 0; j < m; j++) {
          if (text[i + j] !== pattern[j]) {
            match = false;
            break;
          }
        }
        if (match) return i;
      }
      if (i < n - m) {
        windowHash = this.recalcHash(windowHash, text[i], text[i + m], highestBase);
      }
    }
    return -1;
  }
}

// Driver code
const rk = new RabinKarp();
const text = 'ababc';
const pattern = 'abc';
const index = rk.search(text, pattern);
if (index !== -1) {
  console.log(`Pattern found at index ${index}`);
} else {
  console.log('Pattern not found');
}

const patternHash = this.computeHash(pattern, m);

Calculate hash of pattern to compare with text windows

let windowHash = this.computeHash(text, m);

Calculate initial hash of first window in text

if (patternHash === windowHash) {

Check if current window hash matches pattern hash

for (let j = 0; j < m; j++) { if (text[i + j] !== pattern[j]) { match = false; break; } }

Verify characters one by one if hashes match

windowHash = this.recalcHash(windowHash, text[i], text[i + m], highestBase);

Update hash by sliding window one character forward

Output

Pattern found at index 2

Complexity Analysis

Time: O(n + m) because we compute initial hashes in O(m) and slide over text in O(n), verifying matches only when hashes match

Space: O(1) because we use fixed extra space for hashes and counters

vs Alternative: Compared to naive matching O(n*m), Rabin Karp is faster on average by using hash comparisons to skip unnecessary character checks

Edge Cases

pattern longer than text

Returns -1 immediately since pattern cannot fit

DSA Javascript

if (m > n) return -1;

pattern not found in text

Returns -1 after checking all windows

DSA Javascript

return -1;

pattern equals text

Returns 0 as pattern matches at start

DSA Javascript

if (patternHash === windowHash) { ... }

When to Use This Pattern

When you need to find a substring quickly and want to avoid checking every character repeatedly, use Rabin Karp because it uses hashing to speed up comparisons.

Common Mistakes

Mistake: Not verifying characters after hash match, leading to false positives
Fix: Always check characters one by one when hashes match to confirm actual match

Mistake: Not handling negative hash values after recalculation
Fix: Add prime number to hash if it becomes negative to keep it positive

Summary

It finds a pattern in a text by comparing hash values of substrings.

Use it when you want faster substring search than checking every character.

The key is using a rolling hash to quickly update substring hashes as you slide.

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