Rabin Karp String Matching in DSA Typescript - Execution Trace

Concept Flow - Rabin Karp String Matching

Compute pattern hash

↓

Compute initial text window hash

↓

For each window in text

↓

Compare hashes

↓

Check characters

↓

Pattern found

↓

Slide window by 1

→Update hash efficiently

↓

Repeat until end of text

The algorithm computes a hash for the pattern and for each text window, compares hashes, and if equal, checks characters to find matches efficiently.

Execution Sample

DSA Typescript

function rabinKarp(text: string, pattern: string): number[] {
  const result: number[] = [];
  const base = 256, prime = 101;
  let patternHash = 0, windowHash = 0, h = 1;
  const m = pattern.length, n = text.length;
  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;
    windowHash = (base * windowHash + text.charCodeAt(i)) % prime;
  }
  for (let i = 0; i <= n - m; i++) {
    if (patternHash === windowHash) {
      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 = (base * (windowHash - text.charCodeAt(i) * h) + text.charCodeAt(i + m)) % prime;
      if (windowHash < 0) windowHash += prime;
    }
  }
  return result;
}

This code finds all starting indices where the pattern appears in the text using Rabin-Karp hashing.

Execution Table

Step	Operation	Pattern Hash	Window Hash	Window Start Index	Hash Match?	Character Check	Result Indices	Visual State
1	Compute h = base^(m-1) % prime	-	-	-	-	-	[]	-
2	Compute pattern hash	85	-	-	-	-	[]	-
3	Compute initial window hash	-	85	0	Yes	-	[]	Window: text[0..2]
4	Compare hashes at index 0	85	85	0	Yes	Match confirmed	[0]	Window: text[0..2] matches pattern
5	Slide window to index 1	-	23	1	No	-	[0]	Window: text[1..3]
6	Compare hashes at index 1	85	23	1	No	-	[0]	Window: text[1..3] no match
7	Slide window to index 2	-	56	2	No	-	[0]	Window: text[2..4]
8	Compare hashes at index 2	85	56	2	No	-	[0]	Window: text[2..4] no match
9	Slide window to index 3	-	85	3	Yes	-	[0]	Window: text[3..5]
10	Compare hashes at index 3	85	85	3	Yes	Match confirmed	[0,3]	Window: text[3..5] matches pattern
11	Slide window to index 4	-	12	4	No	-	[0,3]	Window: text[4..6]
12	Compare hashes at index 4	85	12	4	No	-	[0,3]	Window: text[4..6] no match
13	End of text reached	-	-	-	-	-	[0,3]	-

💡 Reached end of text windows (index 4), no more windows to check.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 5	After Step 7	After Step 9	Final
patternHash	0	85	85	85	85	85	85
windowHash	0	0	85	23	56	85	12
h	1	26	26	26	26	26	26
result	[]	[]	[]	[0]	[0]	[0,3]	[0,3]
windowStartIndex	-	-	0	1	2	3	4

Key Moments - 3 Insights

Why do we check characters even if the hashes match?

Because different strings can have the same hash (hash collision). The character check confirms the actual match, as shown in steps 4 and 10 where hashes matched and characters were verified.

How is the window hash updated efficiently when sliding?

Instead of recomputing the hash from scratch, we remove the leftmost character's contribution and add the new rightmost character, using the precomputed 'h' value. This is shown in steps 5, 7, 9, and 11.

Why do we add 'prime' if windowHash becomes negative?

Modulo operation can produce negative values in some languages. Adding 'prime' ensures the hash stays positive, keeping comparisons correct, as done after updating windowHash in step 5.

Visual Quiz - 3 Questions

Look at the execution table at step 4. What is the window start index when the first match is found?

A 0

B 1

C 3

D 4

💡 Hint

Check the 'Window Start Index' column at step 4 in the execution table.

At which step does the window hash first become 85?

A Step 2

B Step 3

C Step 5

D Step 9

💡 Hint

Look at the 'Window Hash' column in the execution table and find when it first equals 85.

If the pattern length was increased by 1, how would the variable 'h' change?

A It would be multiplied once more by base and modulo prime

B It would stay the same

C It would be divided by base

D It would be reset to 1

💡 Hint

Refer to the variable_tracker row for 'h' and how it is computed in step 1.

Concept Snapshot

Rabin Karp String Matching:
- Compute hash of pattern and initial text window
- Slide window over text, update hash efficiently
- If hashes match, check characters to confirm
- Uses rolling hash with base and prime modulus
- Efficient for multiple pattern searches
- Handles collisions by character verification

Full Transcript

Rabin Karp String Matching works by first computing a hash value for the pattern and the first window of the text. Then it slides the window over the text one character at a time, updating the hash efficiently by removing the leftmost character and adding the new rightmost character. At each step, it compares the pattern hash and the current window hash. If they match, it checks the characters one by one to confirm the match because different strings can have the same hash. This process continues until the entire text is checked. The variable 'h' is used to remove the leftmost character's contribution from the hash. If the hash becomes negative after updating, we add the prime number to keep it positive. The algorithm returns all starting indices where the pattern is found in the text.

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