🔍 Rabin-Karp Algorithm

Ever tried finding a word in a huge chunk of text and thought,
There has to be a faster way than checking every single character!😩
Enter the Rabin-Karp Algorithm — a smart and efficient way to search for patterns in strings using a clever trick called rolling hash 🪄
Let’s break it down step by step — no jargon, no confusion, just clarity and fun. 🧠✨
🤔 The Problem
You’re given:
Text → "geeksforgeeks"
Pattern → "geek"
And your task is to find all positions where the pattern appears in the text.
✅ Expected Output:
[1, 9] // Using 1-based indexing (because humans count from 1 😅)

🧠 The Big Idea (Why Rabin-Karp Is Smart?)
Instead of comparing every letter of the pattern with every possible substring of the text, what if we could:
1.Convert the pattern into a number (hash)
2.Convert parts of the text into numbers too
3.Compare those numbers instead of characters
→ Much faster than checking each letter!
If the hashes match, we double-check the actual characters — just to be sure (because different strings can sometimes have the same hash — that's called a collision).

🔢 What's a Hash Anyway?
Think of a hash as a string’s fingerprint:
Same strings → same hash
Different strings → usually different hashes
Rabin-Karp uses a rolling hash, which is just a clever way of updating the hash as we move through the text, without recalculating everything from scratch.

🔄Rolling Hash — The Star of the Show🌟
Let’s say we’ve already calculated the hash for "geek" — now we want the hash for the next window: "eeks".
Instead of this:
Recalculate hash("eeks") from scratch 😩

We do this:
t_new = (d * (t_old - old_char * h) + new_char) % q
Where:
-t_old is the previous window’s hash
-old_char is the character sliding out of the window
-new_char is the character sliding into the window
-d is the number of characters in the alphabet (e.g., 256 for extended -ASCII)
-h = d^(M-1) % q is used to remove the effect of the oldest character
-q is a large prime number used to reduce hash collisions

We move the window and get a new hash in constant time! 🔥

💥Why Rabin-Karp is Awesome
✅ Fast search using hashing
✅ Great for multiple pattern searches
✅ Average time complexity: O(N + M)
✅ Used in:
1.Plagiarism detection 🧑‍🎓
2.Big text search engines
3.DNA sequence matching 🧬
4.Intrusion detection systems 🔐

🧾 Dry Run: Let’s See It in Action
🔸 Input:
Text: "geeksforgeeks"
Pattern: "geek"

Step 1: Initialize Variables
M = 4 // length of pattern
N = 13 // length of text
d = 256 // characters in the alphabet
q = 101 // prime number for hashing

Step 2: Compute Hash Multiplier
h = pow(d, M-1) % q = (256^3) % 101 = 88

Step 3: Calculate Initial Hashes
p = hash("geek") % q = 27
t = hash("geek") % q = 27

Step 4: Slide the Window and Compare
Iteration 1: "geek" → Match found ✅ at index 1
Iteration 2: "eeks" → Hash ≠ 27 → skip ❌
Iteration 3: "eksf" → Hash ≠ 27 → skip ❌
...
Iteration 9: "geek" → Match found ✅ at index 9

🧑‍💻Final Result:
[1, 9]

👨‍💻 C++ Code: Rabin-Karp Algorithm

#include <iostream> #include <vector> using namespace std; // Your Rabin-Karp search function vector<int> search(string pattern, string text) { vector<int> result; int d = 256; // Total characters (ASCII) int q = 101; // Prime number to avoid collision int M = pattern.length(); int N = text.length(); int p = 0; // hash for pattern int t = 0; // hash for text window int h = 1; // Step 1: Calculate hash multiplier h = pow(d, M-1) % q for (int i = 0; i < M - 1; i++) h = (h * d) % q; // Step 2: Initial hash values for (int i = 0; i < M; i++) { p = (d * p + pattern[i]) % q; t = (d * t + text[i]) % q; } // Step 3: Slide pattern over text for (int i = 0; i <= N - M; i++) { // If hash values match, check characters one by one if (p == t) { bool match = true; for (int j = 0; j < M; j++) { if (text[i + j] != pattern[j]) { match = false; break; } } if (match) result.push_back(i + 1); // 1-based indexing } // Step 4: Update hash using rolling hash if (i < N - M) { t = (d * (t - text[i] * h) + text[i + M]) % q; if (t < 0) t = t + q; // Make sure hash stays positive } } return result; } // Main Function int main() { string text = "ababcabcabababd"; string pattern = "ababd"; vector<int> positions = search(pattern, text); if (!positions.empty()) { cout << "Pattern found at position(s): "; for (int pos : positions) cout << pos << " "; cout << endl; } else { cout << "Pattern not found in the text." << endl; } return 0; } 

🧠 Key Takeaways
Rabin-Karp is a hash-based string searching algorithm.
It uses a rolling hash to speed up window comparisons.
Perfect for situations where you need to find multiple patterns efficiently.