C++-এ রোলিং হ্যাশ (Rolling Hash) বাস্তবায়ন

রোলিং হ্যাশ কী?

রোলিং হ্যাশ একটি হ্যাশ ফাংশন যেখানে ইনপুট ডেটার একটি উইন্ডো (window) এর মাধ্যমে হ্যাশ গণনা করা হয় এবং উইন্ডোটি স্লাইড করে নেওয়া হয়। রাবিন-কার্প (Rabin-Karp) স্ট্রিং সার্চ অ্যালগরিদম রোলিং হ্যাশের জনপ্রিয় একটি অ্যাপ্লিকেশন।

রাবিন-কার্প হ্যাশ ফাংশন

স্ট্রিং-এর জন্য হ্যাশ মান: H = c₁aᵏ⁻¹ + c₂aᵏ⁻² + ... + cₖa⁰

এখানে a একটি কনস্ট্যান্ট, c₁...cₖ ইনপুট ক্যারেক্টার। বিশাল মান নিয়ন্ত্রণে mod n ব্যবহার করা হয়।

অ্যালগরিদম

CONST P_B = 227, P_M = 1000005

Function hash(string s):
    r = 0
    for each char c in s:
        r = (r * P_B + c) % P_M
    return r

Function rabin_karp(string needle, string haystack):
    h1 = hash(needle)
    h2 = 0
    power = 1
    for i = 0 to needle.size()-1:
        power = (power * P_B) % P_M
    for i = 0 to haystack.size()-1:
        h2 = (h2 * P_B + haystack[i]) % P_M
        if i >= needle.size():
            h2 = (h2 - power * haystack[i-needle.size()] % P_M + P_M) % P_M
        if i >= needle.size()-1 AND h1 == h2:
            return i - (needle.size()-1)
    return -1

উদাহরণ কোড

#include <iostream>
#include <string>
using namespace std;

const int P_B = 227;
const int P_M = 1000005;

int hash(const string& s) {
    int r = 0;
    for (int i = 0; i < s.size(); i++) {
        r = (r * P_B + s[i]) % P_M;
    }
    return r;
}

int rabin_karp(const string& n, const string& hstack) {
    int h1 = hash(n);
    int h2 = 0;
    int power = 1;
    for (int i = 0; i < n.size(); i++)
        power = (power * P_B) % P_M;
    for (int i = 0; i < hstack.size(); i++) {
        h2 = (h2 * P_B + hstack[i]) % P_M;
        if (i >= n.size()) {
            h2 -= (power * hstack[i - n.size()]) % P_M;
            if (h2 < 0) h2 += P_M;
        }
        if (i >= n.size() - 1 && h1 == h2)
            return i - (n.size() - 1);
    }
    return -1;
}

int main() {
    string s1, s2;
    cout << "Enter Input String: "; getline(cin, s1);
    cout << "Enter String to find: "; cin >> s2;
    int pos = rabin_karp(s2, s1);
    if (pos == -1) cout << "String not found" << endl;
    else cout << "String \"" << s2 << "\" found at position " << pos << endl;
    return 0;
}

আউটপুট

Enter Input String: Tutorialspoint
Enter String to find: a
String "a" found at position 6
Enter Input String: Tutorialspoint
Enter String to find: b
String not found

ব্যাখ্যা: রোলিং হ্যাশ স্ট্রিং মিলানের জন্য দ্রুত এবং কার্যকর, বিশেষ করে বড় টেক্সটে প্যাটার্ন সার্চ করার ক্ষেত্রে।