Rabin Karp String Matching in DSA Javascript - Execution Trace

Concept Flow - Rabin Karp String Matching

Start

↓

Compute pattern hash

↓

Compute initial text window hash

↓

For each window in text

↓

Compare hashes

↓

Check exact chars

↓

Report match

↓

Slide window by 1

→Update hash

↓

End

The algorithm slides a window over the text, compares hash values of the pattern and current window, and confirms matches by character comparison if hashes match.

Execution Sample

DSA Javascript

const rabinKarp = (text, pattern) => {
  const pLen = pattern.length;
  const tLen = text.length;
  const base = 256, mod = 101;
  let pHash = 0, tHash = 0, h = 1;
  // Compute h = pow(base, pLen-1) % mod
  for (let i = 0; i < pLen - 1; i++) h = (h * base) % mod;
  // Initial hash for pattern and first window
  for (let i = 0; i < pLen; i++) {
    pHash = (base * pHash + pattern.charCodeAt(i)) % mod;
    tHash = (base * tHash + text.charCodeAt(i)) % mod;
  }
  const results = [];
  for (let i = 0; i <= tLen - pLen; i++) {
    if (pHash === tHash) {
      let match = true;
      for (let j = 0; j < pLen; j++) {
        if (text[i + j] !== pattern[j]) {
          match = false;
          break;
        }
      }
      if (match) results.push(i);
    }
    if (i < tLen - pLen) {
      tHash = (base * (tHash - text.charCodeAt(i) * h) + text.charCodeAt(i + pLen)) % mod;
      if (tHash < 0) tHash += mod;
    }
  }
  return results;
};

This code finds all starting indices where the pattern matches the text using Rabin Karp hashing and sliding window.

Execution Table

Step	Operation	Pattern Hash (pHash)	Text Window Hash (tHash)	Window Start Index (i)	Hash Match?	Exact Match Check	Matches Found	Visual State
1	Compute h = base^(pLen-1) % mod	-	-	-	-	-	-	h=256^(3-1)%101=256^2%101=54
2	Compute initial pHash and tHash for 'abc'	92	92	0	-	-	[]	pHash=92, tHash=92 for 'abc'
3	Compare pHash and tHash at i=0	92	92	0	Yes	-	[]	Window='abc' matches hash
4	Exact char check at i=0	92	92	0	Yes	Yes	[0]	Pattern matches text at index 0
5	Slide window to i=1, update tHash for 'bcd'	92	61	1	No	-	[0]	Window='bcd' hash=61
6	Compare pHash and tHash at i=1	92	61	1	No	-	[0]	No hash match, skip exact check
7	Slide window to i=2, update tHash for 'cde'	92	30	2	No	-	[0]	Window='cde' hash=30
8	Compare pHash and tHash at i=2	92	30	2	No	-	[0]	No hash match, skip exact check
9	Slide window to i=3, update tHash for 'def'	92	99	3	No	-	[0]	Window='def' hash=99
10	Compare pHash and tHash at i=3	92	99	3	No	-	[0]	No hash match, skip exact check
11	End: i=4 exceeds tLen-pLen	92	-	4	-	-	[0]	Search complete

💡 Loop ends when window start index i exceeds text length minus pattern length

Variable Tracker

Variable	Start	After Step 2	After Step 5	After Step 7	After Step 9	Final
pHash	-	92	92	92	92	92
tHash	-	92	61	30	99	99
i (window start)	-	0	1	2	3	4
Matches Found	[]	[]	[0]	[0]	[0]	[0]
h	-	54	54	54	54	54

Key Moments - 3 Insights

Why do we check characters even if the hash matches?

Because different strings can have the same hash (hash collision). The exact character check confirms the match, as shown in step 4 where hash matches and characters are checked.

Why do we update the hash when sliding the window?

To efficiently compute the new window's hash without recalculating from scratch. Step 5 shows updating tHash by removing the left char and adding the new right char.

Why do we add mod if tHash becomes negative after update?

Because modulo operation can produce negative results in some languages. Adding mod keeps tHash positive, ensuring correct comparisons, as done after step 5.

Visual Quiz - 3 Questions

Look at the execution table at step 4. What is the Matches Found array after exact character check?

A [0]

B []

C [1]

D [0,1]

💡 Hint

Check the 'Matches Found' column at step 4 in the execution table.

At which step does the hash of the text window first differ from the pattern hash?

A Step 3

B Step 5

C Step 2

D Step 4

💡 Hint

Look at the 'Hash Match?' column in the execution table to find when it changes from Yes to No.

If the pattern length was 2 instead of 3, how would the variable 'h' change after step 1?

A h would be 256^0 % 101 = 1

B h would be 256^2 % 101 = 54

C h would be 256^1 % 101 = 54

D h would be 256^3 % 101 = 1

💡 Hint

h is computed as base^(pattern length -1) % mod, see step 1 in variable_tracker.

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
- Use modulo to avoid large numbers and handle negatives
- Returns all start indices where pattern matches text

Full Transcript

Rabin Karp algorithm finds pattern matches in text by hashing. It first computes the hash of the pattern and the first window of text. Then it slides the window one character at a time, updating the hash efficiently by removing the leftmost character and adding the new rightmost character. When the hash of the current window matches the pattern hash, it checks characters one by one to confirm the match because different strings can have the same hash. The algorithm uses modulo arithmetic to keep hash values manageable and positive. It 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. 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