C Program
#include <stdio.h>
#include <string.h>
#define d 256
void rabinKarp(char pat[], char txt[], int q) {
int M = strlen(pat);
int N = strlen(txt);
int i, j;
int p = 0; // hash for pattern
int t = 0; // hash for text
int h = 1;
for (i = 0; i < M - 1; i++)
h = (h * d) % q;
for (i = 0; i < M; i++) {
p = (d * p + pat[i]) % q;
t = (d * t + txt[i]) % q;
}
for (i = 0; i <= N - M; i++) {
if (p == t) {
for (j = 0; j < M; j++) {
if (txt[i + j] != pat[j])
break;
}
if (j == M)
printf("Pattern found at index %d\n", i);
}
if (i < N - M) {
t = (d * (t - txt[i] * h) + txt[i + M]) % q;
if (t < 0)
t = (t + q);
}
}
}
int main() {
char txt[] = "ABCCDDAEFG";
char pat[] = "CDD";
int q = 101;
rabinKarp(pat, txt, q);
return 0;
}C Output
Pattern found at index 2
C++ Program
#include <iostream>
using namespace std;
#define d 256
void rabinKarp(string pat, string txt, int q) {
int M = pat.size();
int N = txt.size();
int p = 0, t = 0, h = 1;
for (int i = 0; i < M - 1; i++)
h = (h * d) % q;
for (int i = 0; i < M; i++) {
p = (d * p + pat[i]) % q;
t = (d * t + txt[i]) % q;
}
for (int i = 0; i <= N - M; i++) {
if (p == t) {
int j;
for (j = 0; j < M; j++)
if (txt[i + j] != pat[j])
break;
if (j == M)
cout << "Pattern found at index " << i << endl;
}
if (i < N - M) {
t = (d * (t - txt[i] * h) + txt[i + M]) % q;
if (t < 0)
t = (t + q);
}
}
}
int main() {
string txt = "ABCCDDAEFG";
string pat = "CDD";
int q = 101;
rabinKarp(pat, txt, q);
return 0;
}C++ Output
Pattern found at index 2
JAVA Program
public class RabinKarp {
public final static int d = 256;
static void search(String pat, String txt, int q) {
int M = pat.length();
int N = txt.length();
int p = 0, t = 0, h = 1;
for (int i = 0; i < M - 1; i++)
h = (h * d) % q;
for (int i = 0; i < M; i++) {
p = (d * p + pat.charAt(i)) % q;
t = (d * t + txt.charAt(i)) % q;
}
for (int i = 0; i <= N - M; i++) {
if (p == t) {
int j;
for (j = 0; j < M; j++) {
if (txt.charAt(i + j) != pat.charAt(j))
break;
}
if (j == M)
System.out.println("Pattern found at index " + i);
}
if (i < N - M) {
t = (d * (t - txt.charAt(i) * h) + txt.charAt(i + M)) % q;
if (t < 0)
t = (t + q);
}
}
}
public static void main(String[] args) {
String txt = "ABCCDDAEFG";
String pat = "CDD";
int q = 101;
search(pat, txt, q);
}
}JAVA Output
Pattern found at index 2
Python Program
d = 256
def rabinKarp(pat, txt, q):
M = len(pat)
N = len(txt)
p = 0
t = 0
h = 1
for i in range(M-1):
h = (h * d) % q
for i in range(M):
p = (d * p + ord(pat[i])) % q
t = (d * t + ord(txt[i])) % q
for i in range(N-M+1):
if p == t:
if txt[i:i+M] == pat:
print("Pattern found at index", i)
if i < N-M:
t = (d*(t - ord(txt[i])*h) + ord(txt[i+M])) % q
if t < 0:
t = t + q
txt = "ABCCDDAEFG"
pat = "CDD"
q = 101
rabinKarp(pat, txt, q)Python Output
Pattern found at index 2
Explanation
Example
Consider Rabin-Karp to be looking for a word in a book based on the hash code of the word instead of comparing each character individually. For example, if you wish to look for "CDD" within "ABCCDDAEFG", rather than directly comparing "CDD" with each substring, you first transform both the substring and the pattern into a hash value. If the hash is equal, you then compare character by character. This makes searching significantly quicker in most instances.
Real-Life Analogy
Suppose you are searching for a document within a gigantic pile of documents. Rather than going through each document word for word, you may initially glance at the signature ID (such as a barcode) on every document. If the barcode is equal to the ID for which you are looking, then you open up the document to check the contents. Hashing in Rabin-Karp is similar to that barcode—it allows us to rapidly bypass non-matching candidates.
Why It Matters
Rabin-Karp is significant as it brings the idea of string hashing. Hashing makes comparison time-efficient, particularly when we have to search many patterns within a large piece of text. Plagiarism finding, DNA sequence finding, or searching big logs, for instance, can be made efficient with this algorithm. Rather than brute force character-by-character searching, it reduces useless work in a smart way.
Learning Insights
The important point is that Rabin-Karp has a rolling hash. Rather than re-computing the hash from scratch for each substring, it adapts the hash by subtracting the leftmost character and adding the next character. This significantly improves computation. Hash collisions are possible (two distinct strings giving rise to the same hash), however, so a final check is always necessary.
Interview Use
This problem is commonly asked in coding interviews when the interviewer wants to test understanding of efficient string search and hashing. A brute force search has time complexity O(nm), but Rabin-Karp brings it closer to O(n+m) in average cases. If the interviewer wants to know about string matching in real systems, Rabin-Karp is a very good answer to give.
SEO Optimized Closing
The Rabin-Karp Algorithm is the most efficient string matching algorithm every programmer must learn. It employs rolling hashes to efficiently find potential matches and forms a common part of real-world applications like search engines, plagiarism checkers, and DNA sequence comparators. Learning Rabin-Karp by beginners not only makes them aware of how hashing accelerates algorithms but also solidifies their problem-solving skills for coding interviews. Knowledge of Rabin-Karp algorithm implementation in C, C++, Java, and Python with examples enables students to prepare for exams, competitive programming, and technical interviews with confidence and is one of the most important algorithms in computer science.
Social Plugin