Rabin Karp String Matching in DSA Typescript - Deep Dive

Overview - Rabin Karp String Matching

What is it?

Rabin Karp String Matching is a method to find a smaller pattern inside a bigger text by comparing numbers instead of letters. It changes the pattern and parts of the text into numbers using a formula called hashing. Then it quickly checks if these numbers match to find where the pattern appears.

Why it matters

Without Rabin Karp, searching for patterns in text would be slower because we would compare each letter one by one many times. This method speeds up searching by using math to skip unnecessary checks. It helps in things like finding words in documents, detecting plagiarism, or searching DNA sequences.

Where it fits

Before learning Rabin Karp, you should understand basic string matching and hashing concepts. After this, you can learn more advanced string algorithms like Knuth-Morris-Pratt or Boyer-Moore for faster or specialized searching.

Mental Model

Core Idea

Rabin Karp turns strings into numbers to quickly find matches by comparing these numbers instead of letters.

Think of it like...

Imagine you want to find a page in a book by checking the page number instead of reading every word. If the page number matches the one you want, you then check the words to be sure.

Text:  T H I S I S A T E X T
Pattern: I S A

Hash of Pattern -> number P
Sliding window over Text:
[ T H I ] -> hash1
[ H I S ] -> hash2
[ I S A ] -> hash3
Compare hash3 with P
If equal, check letters to confirm

┌─────────────┐
│ Text String │
└─────────────┘
  ↓ sliding window
┌─────┐ ┌─────┐ ┌─────┐
│ T H I ││ H I S ││ I S A │
└─────┘ └─────┘ └─────┘
  ↓ hash
 n1      n2      n3
  ↓ compare
   P (pattern hash)

Build-Up - 7 Steps

1

Foundation

Understanding Basic String Matching

Concept: Learn how to find a pattern in text by checking each position one by one.

Imagine you want to find the word 'cat' in the sentence 'the cat sat'. You look at every group of three letters in the sentence and compare them to 'cat'. This is called naive string matching.

Result

You find 'cat' starting at position 4 in the sentence.

Understanding the slow, simple way to match strings helps appreciate why faster methods like Rabin Karp are useful.

2

Foundation

Introduction to Hashing Strings

Concept: Learn how to convert strings into numbers using a simple formula.

Assign each letter a number (a=1, b=2, ...). For example, 'abc' becomes 1*base^2 + 2*base^1 + 3*base^0. This number is the hash. It represents the string uniquely in most cases.

Result

The string 'abc' converts to a number like 1*26^2 + 2*26 + 3 = 731.

Hashing lets us compare numbers instead of letters, which is faster for computers.

3

Intermediate

Sliding Window Hash Calculation

🤔Before reading on: Do you think we need to recalculate the hash from scratch for every new substring? Commit to yes or no.

Concept: Learn how to update the hash quickly when moving the window over the text.

Instead of recalculating the hash for each substring, remove the leftmost character's value and add the new rightmost character's value. This is called rolling hash.

Result

Hash for 'abc' is 731, for 'bcd' can be calculated quickly from 731 without full recalculation.

Knowing rolling hash saves time and makes Rabin Karp efficient.

4

Intermediate

Handling Hash Collisions

🤔Before reading on: Do you think two different strings can have the same hash? Commit to yes or no.

Concept: Understand that different strings can sometimes produce the same hash, called a collision.

When hashes match, we must check the actual strings letter by letter to confirm the match. This avoids false positives.

Result

Even if hashes match, only exact string matches are accepted.

Recognizing collisions prevents errors and ensures correct pattern matching.

5

Intermediate

Choosing a Good Hash Base and Modulus

Concept: Learn why picking the right numbers for hashing reduces collisions and overflow.

We use a base (like 256 or 101) and a large prime modulus to keep hash values manageable and unique. This reduces collisions and keeps numbers small.

Result

Hash values stay within a range and collisions become rare.

Good parameters make Rabin Karp reliable and efficient in practice.

6

Advanced

Implementing Rabin Karp in TypeScript

🤔Before reading on: Do you think the algorithm checks every substring fully or only when hashes match? Commit to your answer.

Concept: See a full working example of Rabin Karp string matching in TypeScript.

```typescript function rabinKarp(text: string, pattern: string): number[] { const result: number[] = []; const base = 256; const prime = 101; const m = pattern.length; const n = text.length; let patternHash = 0; let textHash = 0; let h = 1; for (let i = 0; i < m - 1; 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) { 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) { textHash = (base * (textHash - text.charCodeAt(i) * h) + text.charCodeAt(i + m)) % prime; if (textHash < 0) textHash += prime; } } return result; } // Example usage: const positions = rabinKarp('abracadabra', 'abra'); console.log(positions); ```

Result

Output: [0, 7]

Seeing the full code connects theory to practice and shows how rolling hash and collision checks work together.

7

Expert

Optimizing Rabin Karp for Large Texts

🤔Before reading on: Do you think using a single hash is enough for very large texts? Commit to yes or no.

Concept: Learn advanced techniques like double hashing and choosing primes to reduce collisions in big data.

For very large texts, collisions become more likely. Using two different hash functions (double hashing) and carefully chosen primes reduces false matches. Also, modular arithmetic keeps numbers manageable and fast.

Result

Algorithm becomes more reliable and efficient on large inputs.

Understanding these optimizations is key for applying Rabin Karp in real-world, large-scale systems.

Under the Hood

Rabin Karp converts strings into numeric hashes using polynomial rolling hash. It slides a window over the text, updating the hash efficiently by removing the left character and adding the right one. When the pattern hash matches the window hash, it verifies the actual characters to avoid false matches caused by collisions.

Why designed this way?

It was designed to speed up string searching by avoiding repeated character comparisons. The rolling hash allows quick updates without full recomputation. The use of modulus keeps numbers small and manageable. Alternatives like naive search were too slow, and other algorithms like KMP require preprocessing the pattern differently.

┌───────────────┐
│   Pattern     │
│  String ->    │
│  Hash Value   │
└──────┬────────┘
       │
       ▼
┌───────────────┐
│   Text String  │
│ Sliding Window │
│  Hash Update   │
└──────┬────────┘
       │
       ▼
┌───────────────┐
│ Compare Hashes │
│ If match, check│
│ characters     │
└───────────────┘

Myth Busters - 3 Common Misconceptions

Quick: Does a matching hash always mean the strings are the same? Commit to yes or no.

Common Belief: If the hash values match, the strings must be identical.

Reality: Hashes can collide, meaning different strings can have the same hash value.

Why it matters: Assuming hash equality means string equality can cause wrong matches and bugs in applications like plagiarism detection.

Quick: Do you think recalculating the hash from scratch each time is efficient? Commit to yes or no.

Common Belief: We must calculate the hash of every substring fully from the start.

Reality: Rolling hash lets us update the hash quickly without full recalculation.

Why it matters: Not using rolling hash makes the algorithm slow and defeats its purpose.

Quick: Is Rabin Karp always faster than other string matching algorithms? Commit to yes or no.

Common Belief: Rabin Karp is always the fastest string matching algorithm.

Reality: Rabin Karp can be slower if many collisions happen or for small patterns; other algorithms like KMP or Boyer-Moore may be faster in those cases.

Why it matters: Choosing the wrong algorithm can lead to inefficient programs.

Expert Zone

1

The choice of prime modulus affects collision probability and performance subtly; primes close to the machine word size are often best.

2

Double hashing or using multiple hash functions can drastically reduce false positives in large-scale applications.

3

Handling negative hash values after modulus operations is crucial to avoid bugs in rolling hash updates.

When NOT to use

Avoid Rabin Karp when patterns are very short or when worst-case performance matters, as collisions can degrade speed. Use Knuth-Morris-Pratt or Boyer-Moore algorithms instead for guaranteed linear time or better average performance.

Production Patterns

Rabin Karp is used in plagiarism detection tools, DNA sequence analysis, and network intrusion detection where multiple pattern searches happen. It is often combined with other heuristics and hashing improvements for scalability.

Connections

Hash Tables

Both use hashing to convert data into numbers for fast lookup.

Understanding hashing in Rabin Karp helps grasp how hash tables store and retrieve data efficiently.

Cryptographic Hash Functions

Both use hashing but with different goals: Rabin Karp for speed and cryptographic hashes for security.

Knowing the difference clarifies why Rabin Karp uses simple, fast hashes instead of secure but slow cryptographic hashes.

Signal Processing (Sliding Window Filters)

Both use sliding windows to process data incrementally and efficiently.

Recognizing this pattern across fields shows how incremental updates save computation in many areas.

Common Pitfalls

#1 Recalculating the hash from scratch for every substring.

Wrong approach:

for (let i = 0; i <= n - m; i++) {
let hash = 0;
for (let j = 0; j < m; j++) {
hash = (hash * base + text.charCodeAt(i + j)) % prime;
}
if (hash === patternHash) {
// check characters
}
}

Correct approach:

Use rolling hash to update hash in O(1) time:
textHash = (base * (textHash - text.charCodeAt(i) * h) + text.charCodeAt(i + m)) % prime;

Root cause:

Not understanding rolling hash optimization leads to inefficient code.

#2 Skipping character-by-character check after hash match.

Wrong approach:

if (patternHash === textHash) {
result.push(i); // assume match without checking
}

Correct approach:

if (patternHash === textHash) {
for (let j = 0; j < m; j++) {
if (text[i + j] !== pattern[j]) return;
}
result.push(i);
}

Root cause:

Ignoring collisions causes false positives.

#3 Not handling negative hash values after modulus.

Wrong approach:

textHash = (base * (textHash - text.charCodeAt(i) * h) + text.charCodeAt(i + m)) % prime;

Correct approach:

textHash = (base * (textHash - text.charCodeAt(i) * h) + text.charCodeAt(i + m)) % prime;
if (textHash < 0) textHash += prime;

Root cause:

Modulo operation in some languages can produce negative results, causing wrong hash values.

Key Takeaways

Rabin Karp uses hashing to convert strings into numbers for fast pattern searching.

Rolling hash allows efficient updates of hash values when sliding over the text.

Hash collisions require verifying actual characters to avoid false matches.

Choosing good hash parameters reduces collisions and improves performance.

Rabin Karp is powerful but not always the fastest; understanding its limits helps pick the right algorithm.

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