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

Rabin-Karp Algorithm क्या है

Rabin-Karp text के हर chunk को एक quick fingerprint number देने जैसा है और पहले fingerprints compare करते हुए, सिर्फ दो 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 हर position पर सीधे characters compare करने के बजाय pattern के hash values को text में हर एक जैसी length वाली window के hash values से compare करके text में एक pattern search करता है।

उदाहरण: 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

Window आगे slide होते समय इसका hash scratch से recompute करने के बजाय, एक rolling hash outgoing character का contribution हटाकर और incoming character का जोड़कर पिछली window के hash को O(1) में update करता है, जो पूरे scan को तेज़ बनाता है।

उदाहरण: 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

एक matching hash एक असली match की guarantee नहीं देता, क्योंकि अलग strings एक ही hash value में collide हो सकती हैं, इसलिए Rabin-Karp report करने से पहले confirm करने के लिए हमेशा एक direct character-by-character comparison करता है।

उदाहरण: 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

Average में, Rabin-Karp O(n + m) के करीब चलता है, लेकिन एक खराब hash function जो frequent collisions का कारण बनता है extra character comparisons मजबूर करता है, जो इसके worst case को naive approach जैसे O(n × m) की ओर degrade कर सकता है।

उदाहरण: 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 विशेष रूप से तब उपयोगी है जब एक साथ उसी length के कई patterns search कर रहे हों, क्योंकि आप पहले से सभी patterns hash कर सकते हैं और हर text window के hash को उस पूरे set के खिलाफ O(1) per window जांच सकते हैं।

उदाहरण: 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 क्या है · Kadane का Algorithm · Anagram और Frequency Count · String Reversal और 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. #}
आम गलतियां
  1. characters के sum जैसा एक weak hash उपयोग करना, इसलिए "abc" और "cba" collide होते हैं और कई false matches होते हैं।
  2. Hashes match होने पर character-by-character check skip करना, और collisions को असली matches report करना।
  3. Hash rolling करते समय सही power से multiply किए बिना outgoing character हटाना, या modulus जोड़े बिना negative जाना।
चैप्टर सारांश
  • Strings characters के sequences हैं जो reversal और palindrome checks जैसे operations support करते हैं।
  • Anagram checks और frequency counts strings के अंदर characters compare करते हैं।
  • KMP और Rabin-Karp text में एक pattern search करने के algorithms हैं।
🔒

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.