โปรแกรม C++ เพื่อใช้ Rolling Hash

Rolling hash เป็นฟังก์ชันแฮชที่อินพุตถูกแฮชในหน้าต่างที่เลื่อนผ่านอินพุต

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

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

H=c1ak-1+c2ak-2+….+ cka0.

โดยที่ a เป็นค่าคงที่ และ c₁ , c₂ ….c_k เป็นอักขระอินพุต เพื่อจัดการกับค่ามหาศาลของ H นั้น mod 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.

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

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

ผลลัพธ์

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