โปรแกรม C++ สำหรับการนำ Rolling Hash มาใช้งาน

Rolling Hash เป็นฟังก์ชันแฮชที่คำนวณค่าแฮชของข้อมูลในหน้าต่างเลื่อน (Sliding Window) ที่เคลื่อนผ่านข้อมูลนำเข้า

อัลกอริทึม Rabin-Karp เป็นแอปพลิเคชันยอดนิยมของ Rolling Hash ฟังก์ชันแฮชแบบเลื่อนที่ Rabin และ Karp เสนอ คำนวณค่าเป็นจำนวนเต็ม สำหรับสตริง ค่าจำนวนเต็มนี้คือค่าตัวเลขของสตริงนั้น

อัลกอริทึมค้นหาสตริง Rabin-Karp มักอธิบายด้วยฟังก์ชันแฮชแบบเลื่อนที่เรียบง่าย ซึ่งใช้เพียงการคูณและบวกเท่านั้น:

H = c₁aᵏ⁻¹ + c₂aᵏ⁻² + … + cₖa⁰

โดยที่ a เป็นค่าคงที่ และ c₁, c₂ … cₖ เป็นตัวอักษรนำเข้า เพื่อจัดการค่า H ที่ใหญ่โต จะนำไป modulo n

อัลกอริทึม

Begin
    Declare constant P_B = 227
    Declare constant P_M = 1000005
    Declare function hash(string s)
        int r = 0
        for i = 0 to s.size()-1
            r = r * P_B + s[i]
            r %= P_M
        return r
    Declare function rabin_karp(string n, string hstack)
        int h1 = hash(n)
        int h2 = 0, power = 1
        for i = 0 to n.size()-1
            power = (power * P_B) % P_M
        for i = 0 to hstack.size()-1
            h2 = h2 * P_B + hstack[i]
            h2 %= 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 and h1 == h2
                return i - (n.size()-1)
        return -1
    Declare strings s1, s2
    Print "Enter Input String:"; getline(s1)
    Print "Enter string to find:"; input s2
    if rabin_karp(s2, s1) == -1 print "String not found"
    else print found position
End.

โค้ดตัวอย่าง

#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];
        r %= P_M;
    }
    return r;
}

int rabin_karp(const string& n, const string& hstack) {
    int h1 = hash(n);
    int h2 = 0, 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];
        h2 %= 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;
    if (rabin_karp(s2, s1) == -1)
        cout << "String not found" << endl;
    else
        cout << "String " << s2 << " found at position " << rabin_karp(s2, s1) << 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