Why Rabin Karp String Matching in DSA Python?

The Big Idea

What if you could find a needle in a haystack by just checking the shape of the hay instead of every straw?

The Scenario

Imagine you have a huge book and you want to find every place where a certain sentence appears. You try reading every word and comparing it to your sentence, one by one.

The Problem

This manual way is very slow and tiring. You keep checking the same words again and again, and it's easy to make mistakes or miss some matches because you have to compare each letter every time.

The Solution

Rabin Karp uses a clever trick: it turns each part of the text into a number (called a hash) and compares these numbers instead of letters. This way, it quickly skips parts that don't match and only checks letters when the numbers match, saving a lot of time.

Before vs After

✗ Before

for i in range(len(text) - len(pattern) + 1):
    if text[i:i+len(pattern)] == pattern:
        print('Found at', i)

✓ After

pattern_hash = hash(pattern)
for i in range(len(text) - len(pattern) + 1):
    if hash(text[i:i+len(pattern)]) == pattern_hash:
        print('Found at', i)

What It Enables

This method makes searching for patterns in large texts fast and efficient, even when the text is huge.

Real Life Example

Search engines use this to quickly find your search words inside billions of web pages without checking every letter one by one.

Key Takeaways

Manual letter-by-letter search is slow and error-prone.

Rabin Karp uses hashing to speed up pattern matching.

It quickly skips non-matching parts and checks letters only when needed.