Rabin Karp String Matching in DSA Python - Execution Trace

Concept Flow - Rabin Karp String Matching

Start

↓

Compute pattern hash

↓

Compute initial text window hash

↓

For each text window

↓

Compare hashes

↓

Check exact chars

↓

Slide window by 1

↓

Repeat until end of text

↓

End

The algorithm computes a hash for the pattern and for each window of text. It compares hashes first, then characters if hashes match, sliding the window until the end.

Execution Sample

DSA Python

def rabin_karp(text, pattern):
    p_len = len(pattern)
    p_hash = hash(pattern)
    for i in range(len(text) - p_len + 1):
        window = text[i:i+p_len]
        if hash(window) == p_hash and window == pattern:
            print(f"Match at index {i}")

This code slides over the text, compares hash of each window with pattern hash, then confirms by direct string comparison.

Execution Table

Step	Operation	Current Window	Pattern Hash	Window Hash	Hash Match?	Exact Match?	Action	Visual State
1	Compute pattern hash	-	hash('abc')=963	-	-	-	-	Pattern hash=963
2	Compute initial window hash	text[0:3]='abc'	963	hash('abc')=963	Yes	-	-	Window='abc' hash=963
3	Compare exact strings	abc	963	963	Yes	Yes	Report match at index 0	Match at index 0
4	Slide window by 1	text[1:4]='bcd'	963	hash('bcd')=964	No	-	No match	Window='bcd' hash=964
5	Slide window by 1	text[2:5]='cde'	963	hash('cde')=965	No	-	No match	Window='cde' hash=965
6	Slide window by 1	text[3:6]='def'	963	hash('def')=966	No	-	No match	Window='def' hash=966
7	End	-	963	-	-	-	-	No more windows

💡 Reached end of text windows; all possible matches checked.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 4	After Step 5	After Step 6	Final
p_hash	-	963	963	963	963	963	963
window	-	-	'abc'	'bcd'	'cde'	'def'	-
window_hash	-	-	963	964	965	966	-
current_index	-	-	0	1	2	3	-

Key Moments - 3 Insights

Why do we compare the actual strings after hash match?

Because different strings can have the same hash (hash collision). The execution_table rows 3 and 4 show hash matches but exact string check confirms real match.

How does sliding the window update the hash efficiently?

In this simple example, hash is recomputed fully each time (rows 4-6). In optimized Rabin-Karp, rolling hash updates by removing left char and adding right char.

Why does the loop stop at len(text) - len(pattern) + 1?

Because windows beyond that length would be shorter than the pattern and cannot match. The exit at row 7 shows no more windows to check.

Visual Quiz - 3 Questions

Look at the execution_table, what is the window hash at step 4?

A 963

B 964

C 965

D 966

💡 Hint

Check the 'Window Hash' column at step 4 in the execution_table.

At which step does the algorithm report a match?

A Step 2

B Step 3

C Step 4

D Step 5

💡 Hint

Look at the 'Action' column for when 'Report match' happens.

If the pattern was 'bcd', at which step would the first match be reported?

A Step 2

B Step 3

C Step 4

D Step 5

💡 Hint

Check the 'Current Window' and 'Action' columns to see when 'bcd' window appears.

Concept Snapshot

Rabin Karp String Matching:
- Compute hash of pattern
- Slide window over text, compute window hash
- If hashes match, compare strings
- Report match if exact
- Efficient with rolling hash (not shown here)
- Stops when windows run out

Full Transcript

Rabin Karp string matching works by first computing a hash value for the pattern. Then it slides a window of the same length over the text, computing the hash for each window. If the window hash matches the pattern hash, it compares the actual strings to confirm a match. This avoids unnecessary string comparisons. The process repeats until all possible windows in the text are checked. The example code computes full hashes each time, but optimized versions use rolling hash to update hashes efficiently. The execution table shows each step, the current window, hashes, and actions taken. Matches are reported only after confirming exact string equality. The loop stops when no more windows of pattern length remain in the text.

Practice

1. What is the main idea behind the Rabin Karp String Matching algorithm?

easy

A. It uses hashing to find pattern matches efficiently.

B. It compares each character one by one without hashing.

C. It sorts the text before searching for the pattern.

D. It uses recursion to find the pattern in the text.

Solution

1. Step 1: Understand Rabin Karp's approach

   The algorithm uses a hash function to convert the pattern and text substrings into numbers.

2. Step 2: Use hashing for efficient matching

   By comparing hash values instead of characters, it quickly finds potential matches.

3. Final Answer:

   It uses hashing to find pattern matches efficiently. -> Option A

4. Quick Check:

   Hashing = Efficient matching [OK]

Hint: Remember: Rabin Karp uses hashing for fast pattern search [OK]

Common Mistakes:

• Thinking it compares characters directly without hashing
• Confusing it with sorting-based algorithms
• Assuming it uses recursion

2. Which of the following is the correct way to compute the rolling hash in Rabin Karp for the next substring?

easy

A. new_hash = old_hash * old_char + new_char

B. new_hash = old_hash + old_char - new_char

C. new_hash = (old_hash - old_char * base^(m-1)) * base + new_char

D. new_hash = old_hash / base + new_char * base^(m-1)

Solution

1. Step 1: Recall rolling hash formula

   Rolling hash removes the old char's contribution and adds the new char's value.

2. Step 2: Apply formula correctly

   It subtracts old_char * base^(m-1), multiplies by base, then adds new_char.

3. Final Answer:

   new_hash = (old_hash - old_char * base^(m-1)) * base + new_char -> Option C

4. Quick Check:

   Rolling hash formula = new_hash = (old_hash - old_char * base^(m-1)) * base + new_char [OK]

Hint: Subtract old char, multiply by base, add new char [OK]

Common Mistakes:

• Adding old_char instead of subtracting
• Dividing instead of multiplying by base
• Ignoring power of base for old_char

3. What will be the output of the following code snippet using Rabin Karp to find pattern 'abc' in text 'ababc'?

def rabin_karp(text, pattern):
    base = 256
    prime = 101
    m = len(pattern)
    n = len(text)
    pattern_hash = 0
    text_hash = 0
    h = 1

    for i in range(m-1):
        h = (h * base) % prime

    for i in range(m):
        pattern_hash = (base * pattern_hash + ord(pattern[i])) % prime
        text_hash = (base * text_hash + ord(text[i])) % prime

    for i in range(n - m + 1):
        if pattern_hash == text_hash:
            if text[i:i+m] == pattern:
                return i
        if i < n - m:
            text_hash = (base * (text_hash - ord(text[i]) * h) + ord(text[i + m])) % prime
            if text_hash < 0:
                text_hash += prime
    return -1

print(rabin_karp('ababc', 'abc'))

medium

A. 0

B. 1

C. -1

D. 2

Solution

1. Step 1: Calculate pattern and initial text hash

   Pattern 'abc' length 3, initial text substring 'aba'. Hashes differ, so move forward.

2. Step 2: Slide over text and compare hashes

   At index 1, substring 'bab' hash differs. At index 2, substring 'abc' hash matches pattern hash and strings match.

3. Final Answer:

   2 -> Option D

4. Quick Check:

   Pattern found at index 2 [OK]

Hint: Check hash then substring; match at index 2 [OK]

Common Mistakes:

• Returning first hash match without substring check
• Confusing index positions
• Ignoring negative hash adjustment

4. Identify the bug in this Rabin Karp implementation snippet:

text_hash = (base * (text_hash - ord(text[i]) * h) + ord(text[i + m])) % prime
if text_hash < 0:
    text_hash = text_hash - prime

medium

A. The negative hash correction should add prime, not subtract.

B. The subtraction of ord(text[i]) * h is incorrect.

C. The modulo operation should be done after adding prime.

D. The base should be added, not multiplied.

Solution

1. Step 1: Understand negative hash correction

   If hash is negative after modulo, add prime to make it positive.

2. Step 2: Identify incorrect operation

   Code subtracts prime instead of adding it, causing wrong hash values.

3. Final Answer:

   The negative hash correction should add prime, not subtract. -> Option A

4. Quick Check:

   Negative hash fix = add prime [OK]

Hint: Add prime if hash is negative, never subtract [OK]

Common Mistakes:

• Subtracting prime instead of adding
• Ignoring negative hash values
• Misplacing modulo operation

5. Given a large text and multiple patterns, which modification to Rabin Karp helps efficiently find all patterns in the text?

hard

A. Run Rabin Karp separately for each pattern without optimization.

B. Use a combined hash set of all patterns and check text substrings against it.

C. Sort all patterns and use binary search on text substrings.

D. Use recursion to search each pattern in the text.

Solution

1. Step 1: Understand multiple pattern search challenge

   Running Rabin Karp separately for each pattern is inefficient for many patterns.

2. Step 2: Use combined hashing approach

   Hash all patterns and store in a set. Then check each text substring's hash against this set for quick matches.

3. Final Answer:

   Use a combined hash set of all patterns and check text substrings against it. -> Option B

4. Quick Check:

   Combined hash set = efficient multi-pattern search [OK]

Hint: Hash all patterns once, check text hashes against set [OK]

Common Mistakes:

• Running separate searches for each pattern
• Sorting patterns instead of hashing
• Using recursion unnecessarily