← Back to DSA Course | Chapter 3: Strings | Lesson 6 of 6

Rabin-Karp Algorithm

Rabin-Karp is like giving each chunk of text a quick fingerprint number and comparing fingerprints first, only looking closely when two match.

In this page:

  1. Hashing Idea
  2. Rolling Hash
  3. Pattern Search
  4. Time Complexity
  5. Rabin-Karp Practice
Syntax
markup 
pattern_hash = hash_of(pattern)
for i in range(len(text) - m + 1):
    if window_hash == pattern_hash and text[i:i + m] == pattern:
        return i
    window_hash = roll(window_hash)    # update rolling hash

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;
}

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;
}

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;
}

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;
}

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;
}
Related Topics

KMP Algorithm · Kadanes Algorithm · Anagram and Frequency Count · String Reversal and Palindrome

{# common_mistakes/chapter_summary/browser_support: on Hindi pages the view already swaps in the hi_ translation fields (or blanks these out if untranslated), so this renders correctly for both languages without a lang_code check here. #}
Common Mistakes
  1. Using a weak hash such as the sum of characters, so "abc" and "cba" collide and many false matches occur.
  2. Skipping the character-by-character check when the hashes match, and reporting collisions as real matches.
  3. Removing the outgoing character when rolling the hash without multiplying by the right power, or going negative without adding the modulus.
Chapter Summary
  • Strings are sequences of characters that support operations like reversal and palindrome checks.
  • Anagram checks and frequency counts compare characters within strings.
  • KMP and Rabin-Karp are algorithms for searching a pattern in text.
🔒

Chapter Quiz — Complete all 6 topics to unlock

0/6 topics done

Complete these topics first:

← Previous Lesson KMP Algorithm Next Lesson → Singly Linked List

Login to run this code

C/C++/Java/PHP execution requires a free account. Your code is saved — you'll land right back in the editor after logging in.