Rabin Karp String Matching in DSA Typescript

Mental Model

We use a number to represent a string part and slide over the text, quickly checking if parts match by comparing numbers first.

Analogy: Imagine checking if a small picture is inside a big picture by comparing a simple color code instead of every pixel, then confirming only if codes match.

Text:  T -> h -> i -> s ->   -> i -> s ->   -> a ->   -> t -> e -> x -> t -> null
Pattern:       P -> a -> t -> t -> e -> r -> n -> null
Hash window:  [T h i s] -> slide right -> [h i s ] -> ...
↑ current hash window

Dry Run Walkthrough

Input: text: "ababcabc", pattern: "abc"

Goal: Find all starting positions where pattern "abc" appears in text.

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

pattern hash = hash("abc")
window hash = hash("aba")

Why: We need initial hashes to start comparing pattern with text windows

Step 2: Compare pattern hash and window hash; they differ, so move window right by one

window moves to "bab"; recalculate window hash

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

Step 3: Compare pattern hash and window hash for "bab"; differ, slide window right

window moves to "abc"; recalculate window hash

Why: Keep sliding until hashes match or text ends

Step 4: Pattern hash equals window hash for "abc"; verify characters match

"abc" matches pattern exactly at index 2

Why: Hash collision possible, so confirm actual substring matches

Step 5: Slide window right to "bca"; recalculate hash and compare

window hash differs from pattern hash; no match

Why: Continue searching for other matches

Step 6: Slide window right to "cab"; recalculate hash and compare

window hash differs; no match

Why: No match here, keep sliding

Step 7: Slide window right to "abc"; recalculate hash and compare

window hash equals pattern hash; verify characters

Why: Possible match found, verify to confirm

Step 8: Characters match exactly; record match at index 5

Match found at index 5

Why: Pattern found again in text

Result:

Matches at indices 2 and 5 in text: ababcabc
Result: 2, 5

Annotated Code

DSA Typescript

class RabinKarp {
  private readonly base = 256; // number of characters in input alphabet
  private readonly prime = 101; // a prime number for modulo

  private calculateHash(str: string, length: number): number {
    let hash = 0;
    for (let i = 0; i < length; i++) {
      hash = (hash * this.base + str.charCodeAt(i)) % this.prime;
    }
    return hash;
  }

  private recalculateHash(oldHash: number, leftChar: string, rightChar: string, patternLen: number): number {
    let newHash = oldHash - (leftChar.charCodeAt(0) * Math.pow(this.base, patternLen - 1)) % this.prime;
    newHash = (newHash * this.base + rightChar.charCodeAt(0)) % this.prime;
    if (newHash < 0) {
      newHash += this.prime;
    }
    return newHash;
  }

  public search(text: string, pattern: string): number[] {
    const n = text.length;
    const m = pattern.length;
    const result: number[] = [];
    if (m > n) return result;

    const patternHash = this.calculateHash(pattern, m);
    let windowHash = this.calculateHash(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) {
          result.push(i);
        }
      }
      if (i < n - m) {
        windowHash = this.recalculateHash(windowHash, text[i], text[i + m], m);
      }
    }
    return result;
  }
}

// Driver code
const rk = new RabinKarp();
const text = "ababcabc";
const pattern = "abc";
const matches = rk.search(text, pattern);
console.log(matches.join(", "));

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

Calculate initial hash of the pattern

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

Calculate initial hash of the 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 to avoid false positive from hash collision

if (i < n - m) { windowHash = this.recalculateHash(windowHash, text[i], text[i + m], m); }

Slide window by recalculating hash efficiently

Output

2, 5

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 hash calculations and result storage proportional to matches

vs Alternative: Compared to naive substring search O(n*m), Rabin-Karp is faster on average by using hashing to skip unnecessary character comparisons

Edge Cases

pattern longer than text

returns empty result immediately

DSA Typescript

if (m > n) return result;

empty pattern

returns empty result as no meaningful search

DSA Typescript

if (m > n) return result;

pattern equals text

returns index 0 as match

DSA Typescript

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

When to Use This Pattern

When you need to find a pattern inside a large text efficiently and want to avoid checking every character repeatedly, use Rabin-Karp because it uses hashing to quickly skip non-matching parts.

Common Mistakes

Mistake: Not verifying characters after hash match, leading to false positives due to hash collisions
Fix: Always compare characters one by one when hashes match before reporting a match

Mistake: Incorrectly recalculating rolling hash causing negative values or wrong hash
Fix: Add prime modulus after subtraction and multiplication to keep hash positive and correct

Summary

It finds all occurrences of a pattern in a text using hashing to speed up comparisons.

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

The key insight is using a rolling hash to quickly compare parts of the text without checking every character each time.

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