Rolling hash là một hàm băm trong đó đầu vào được băm trong một cửa sổ di chuyển qua đầu vào.
Rabin-Karp là ứng dụng phổ biến của băm cuộn. Hàm băm cuộn được đề xuất bởi Rabin và Karp tính toán một giá trị nguyên. Đối với một chuỗi giá trị số nguyên là giá trị số của một chuỗi.
Thuật toán tìm kiếm chuỗi Rabin – Karp thường được giải thích bằng cách sử dụng một hàm băm cuộn rất đơn giản chỉ sử dụng phép nhân và phép cộng -
H=c1ak-1+c2ak-2+….+ cka0.
Trong đó, a là hằng số và c 1 , c 2 … .C k là các ký tự đầu vào. Để thao tác giá trị lớn của H, mod n được thực hiện.
Thuật toán
Begin Declare a constant variable P_B of the integer datatype. Initialize P_B= 227. Declare a constant variable P_M of the integer datatype. Initialize P_M= 1000005. Declare a hash() function Pass a string s as parameter. Declare r of the integer datatype. Initialize r = 0. for (int i = 0; i < s.size(); i++) r = r* P_B + s[i] r %= P_M return r Declare function rabin_karp(const string& n, const string& hstack) Declare h1 of the integer datatype. Initialize h1 = hash(n). Declare h2 of the integer datatype. Initialize h2 = 0. Declare power of the integer datatype. Initialize 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; Declare s1 and s2 to the string type. Print “Enter Input String:” Call getline(line, s1) to enter the string. Print “Enter string to find:” Take input for s2. if(rabin_karp(s2, s1) == -1) print” String not found” else print the string. End.
Mã mẫu
#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;
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];
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;
} Đầu ra
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