Rabin Karp String Matching in DSA Python - Build from Scratch

Rabin Karp String Matching

📖 Scenario: You are building a simple text search tool that finds if a small pattern exists inside a larger text. This is like searching for a word in a book.

🎯 Goal: Implement the Rabin Karp algorithm to find the first position of a pattern string inside a text string using hashing.

📋 What You'll Learn

Create variables for the text and pattern strings

Set up variables for the hashing base and modulus

Calculate initial hash values for pattern and first window of text

Slide over the text to check for matching hash and then verify characters

Print the starting index of the first match or -1 if no match

💡 Why This Matters

🌍 Real World

Text search is used in search engines, editors, and DNA sequence analysis to quickly find patterns.

💼 Career

Understanding Rabin Karp helps in roles involving text processing, software development, and algorithm optimization.

1

Create the text and pattern strings

Create a variable called text and set it to the string "abracadabra". Create another variable called pattern and set it to the string "cada".

DSA Python

# Create variables text and pattern with given strings
# Your code here

Hint

Use simple string assignment like text = "abracadabra".

2

Set up hashing base and modulus

Create a variable called base and set it to 256. Create another variable called modulus and set it to 101. These will be used for hashing.

DSA Python

text = "abracadabra"
pattern = "cada"
# Create base and modulus variables for hashing
# Your code here

Hint

Use base = 256 and modulus = 101 exactly.

3

Calculate initial hashes and implement Rabin Karp logic

Create variables pattern_hash and text_hash and set them to 0. Create a variable h and set it to 1. Calculate h as (base ** (len(pattern) - 1)) % modulus. Use a for loop with variable i from 0 to len(pattern) - 1 to calculate the initial hash values for pattern_hash and text_hash. Then use a for loop with variable i from 0 to len(text) - len(pattern) + 1 to slide over the text, check if hashes match, and if so, verify characters one by one. If a match is found, set a variable result to the starting index i and break the loop. If no match is found, set result to -1.

DSA Python

text = "abracadabra"
pattern = "cada"
base = 256
modulus = 101
# Calculate initial hashes and implement Rabin Karp search
# Your code here

Hint

Calculate h first, then initial hashes, then slide over text checking hashes and characters.

4

Print the result index

Write a print statement to display the value of the variable result.

DSA Python

text = "abracadabra"
pattern = "cada"
base = 256
modulus = 101
pattern_hash = 0
text_hash = 0
h = 1
for i in range(len(pattern) - 1):
    h = (h * base) % modulus
for i in range(len(pattern)):
    pattern_hash = (base * pattern_hash + ord(pattern[i])) % modulus
    text_hash = (base * text_hash + ord(text[i])) % modulus
result = -1
for i in range(len(text) - len(pattern) + 1):
    if pattern_hash == text_hash:
        match = True
        for j in range(len(pattern)):
            if text[i + j] != pattern[j]:
                match = False
                break
        if match:
            result = i
            break
    if i < len(text) - len(pattern):
        text_hash = (base * (text_hash - ord(text[i]) * h) + ord(text[i + len(pattern)])) % modulus
        if text_hash < 0:
            text_hash += modulus
# Print the result variable
# Your code here

Hint

Use print(result) to show the index.