Rabin-Karp Algorithm
In this page:
Hashing Idea
Rabin-Karp searches for a pattern in a text by comparing hash values of the pattern against hash values of every same-length window in the text, rather than comparing characters directly at every position.
Example: Hashing Idea
#include <iostream>
using namespace std;
int hashOf(string s) { int h = 0; for (char c : s) h += c; return h; }
int main() {
string text = "abcde", pat = "cde";
int patHash = hashOf(pat);
int m = pat.size();
for (int i = 0; i + m <= (int)text.size(); i++) {
string window = text.substr(i, m);
cout << "Window \"" << window << "\" hash=" << hashOf(window) << (hashOf(window) == patHash ? " MATCH" : "") << endl;
}
return 0;
}public class Main {
static int hashOf(String s) { int h = 0; for (char c : s.toCharArray()) h += c; return h; }
public static void main(String[] args) {
String text = "abcde", pat = "cde";
int patHash = hashOf(pat), m = pat.length();
for (int i = 0; i + m <= text.length(); i++) {
String window = text.substring(i, i + m);
System.out.println("Window \"" + window + "\" hash=" + hashOf(window) + (hashOf(window) == patHash ? " MATCH" : ""));
}
}
}def hash_of(s):
return sum(ord(c) for c in s)
text, pat = "abcde", "cde"
pat_hash, m = hash_of(pat), len(pat)
for i in range(len(text) - m + 1):
window = text[i:i + m]
mark = " MATCH" if hash_of(window) == pat_hash else ""
print(f'Window "{window}" hash={hash_of(window)}{mark}')#include <stdio.h>
#include <string.h>
int hashOf(char *s, int len) { int h = 0; for (int i = 0; i < len; i++) h += s[i]; return h; }
int main() {
char text[] = "abcde", pat[] = "cde";
int m = strlen(pat), patHash = hashOf(pat, m);
for (int i = 0; i + m <= (int)strlen(text); i++) {
int h = hashOf(text + i, m);
printf("Window \"%.*s\" hash=%d%s\n", m, text + i, h, h == patHash ? " MATCH" : "");
}
return 0;
}Login to try C/C++/Java code in the editor
Rolling Hash
Instead of recomputing a window's hash from scratch as it slides forward, a rolling hash updates the previous window's hash in O(1) by removing the outgoing character's contribution and adding the incoming character's, which is what makes the whole scan fast.
Example: Rolling Hash
#include <iostream>
using namespace std;
int main() {
string text = "abcde";
int m = 3;
int h = 0;
for (int i = 0; i < m; i++) h += text[i];
cout << "Window \"" << text.substr(0, m) << "\" hash=" << h << endl;
h = h - text[0] + text[m];
cout << "Window \"" << text.substr(1, m) << "\" hash=" << h << " (rolled in O(1))" << endl;
return 0;
}public class Main {
public static void main(String[] args) {
String text = "abcde";
int m = 3, h = 0;
for (int i = 0; i < m; i++) h += text.charAt(i);
System.out.println("Window \"" + text.substring(0, m) + "\" hash=" + h);
h = h - text.charAt(0) + text.charAt(m);
System.out.println("Window \"" + text.substring(1, 1 + m) + "\" hash=" + h + " (rolled in O(1))");
}
}text = "abcde"
m = 3
h = sum(ord(c) for c in text[:m])
print(f'Window "{text[:m]}" hash={h}')
h = h - ord(text[0]) + ord(text[m])
print(f'Window "{text[1:1+m]}" hash={h} (rolled in O(1))')#include <stdio.h>
int main() {
char text[] = "abcde";
int m = 3, h = 0;
for (int i = 0; i < m; i++) h += text[i];
printf("Window \"%.*s\" hash=%d\n", m, text, h);
h = h - text[0] + text[m];
printf("Window \"%.*s\" hash=%d (rolled in O(1))\n", m, text + 1, h);
return 0;
}Login to try C/C++/Java code in the editor
Pattern Search
A matching hash doesn't guarantee a real match, since different strings can collide to the same hash value, so Rabin-Karp always does a direct character-by-character comparison to confirm before reporting a match.
Example: Pattern Search
#include <iostream>
using namespace std;
int main() {
string text = "abcde", pat = "cde";
int m = pat.size();
for (int i = 0; i + m <= (int)text.size(); i++) {
string window = text.substr(i, m);
if (window == pat) { cout << "Hash matched at " << i << ", confirmed by direct compare" << endl; }
}
return 0;
}public class Main {
public static void main(String[] args) {
String text = "abcde", pat = "cde";
int m = pat.length();
for (int i = 0; i + m <= text.length(); i++) {
if (text.substring(i, i + m).equals(pat)) System.out.println("Hash matched at " + i + ", confirmed by direct compare");
}
}
}text, pat = "abcde", "cde"
m = len(pat)
for i in range(len(text) - m + 1):
if text[i:i + m] == pat:
print(f"Hash matched at {i}, confirmed by direct compare")#include <stdio.h>
#include <string.h>
int main() {
char text[] = "abcde", pat[] = "cde";
int m = strlen(pat);
for (int i = 0; i + m <= (int)strlen(text); i++) {
if (strncmp(text + i, pat, m) == 0) printf("Hash matched at %d, confirmed by direct compare\n", i);
}
return 0;
}Login to try C/C++/Java code in the editor
Time Complexity
On average, Rabin-Karp runs close to O(n + m), but a poor hash function that causes frequent collisions forces extra character comparisons, which can degrade its worst case toward O(n × m), same as the naive approach.
Example: Time Complexity
#include <iostream>
using namespace std;
int main() {
int n = 1000, m = 5;
cout << "Average case: O(n+m) = " << n + m << endl;
cout << "Worst case with many collisions: O(n*m) = " << n * m << endl;
return 0;
}public class Main {
public static void main(String[] args) {
int n = 1000, m = 5;
System.out.println("Average case: O(n+m) = " + (n + m));
System.out.println("Worst case with many collisions: O(n*m) = " + (n * m));
}
}n, m = 1000, 5
print("Average case: O(n+m) =", n + m)
print("Worst case with many collisions: O(n*m) =", n * m)#include <stdio.h>
int main() {
int n = 1000, m = 5;
printf("Average case: O(n+m) = %d\n", n + m);
printf("Worst case with many collisions: O(n*m) = %d\n", n * m);
return 0;
}Login to try C/C++/Java code in the editor
Rabin-Karp Practice
Rabin-Karp is especially useful when searching for multiple patterns of the same length at once, since you can hash all the patterns up front and check each text window's hash against that whole set in O(1) per window.
Example: Rabin-Karp Practice
#include <iostream>
#include <set>
using namespace std;
int hashOf(string s) { int h = 0; for (char c : s) h += c; return h; }
int main() {
set<int> patternHashes = {hashOf("cde"), hashOf("bcd")};
string text = "abcde";
int m = 3;
for (int i = 0; i + m <= (int)text.size(); i++) {
string window = text.substr(i, m);
if (patternHashes.count(hashOf(window))) cout << "Window \"" << window << "\" matches a pattern" << endl;
}
return 0;
}import java.util.HashSet;
public class Main {
static int hashOf(String s) { int h = 0; for (char c : s.toCharArray()) h += c; return h; }
public static void main(String[] args) {
HashSet<Integer> patternHashes = new HashSet<>();
patternHashes.add(hashOf("cde")); patternHashes.add(hashOf("bcd"));
String text = "abcde";
int m = 3;
for (int i = 0; i + m <= text.length(); i++) {
String window = text.substring(i, i + m);
if (patternHashes.contains(hashOf(window))) System.out.println("Window \"" + window + "\" matches a pattern");
}
}
}def hash_of(s):
return sum(ord(c) for c in s)
pattern_hashes = {hash_of("cde"), hash_of("bcd")}
text, m = "abcde", 3
for i in range(len(text) - m + 1):
window = text[i:i + m]
if hash_of(window) in pattern_hashes:
print(f'Window "{window}" matches a pattern')#include <stdio.h>
#include <string.h>
int hashOf(char *s, int len) { int h = 0; for (int i = 0; i < len; i++) h += s[i]; return h; }
int main() {
int patternHashes[2];
patternHashes[0] = hashOf("cde", 3);
patternHashes[1] = hashOf("bcd", 3);
char text[] = "abcde";
int m = 3;
for (int i = 0; i + m <= (int)strlen(text); i++) {
int h = hashOf(text + i, m);
if (h == patternHashes[0] || h == patternHashes[1]) printf("Window \"%.*s\" matches a pattern\n", m, text + i);
}
return 0;
}Login to try C/C++/Java code in the editor
🔒
Chapter Quiz — Complete all 6 topics to unlock
0/6 topics done
Complete these topics first: