用于实现滚动哈希的C ++程序

滚动哈希是一种哈希函数,其中,输入在移动通过输入的窗口中被哈希。

Rabin-Karp是滚动哈希的流行应用。Rabin和Karp提出的滚动哈希函数计算一个整数值。对于字符串,整数值是字符串的数值。

通常使用非常简单的滚动哈希函数解释Rabin–Karp字符串搜索算法,该函数仅使用乘法和加法-

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

其中,a为常数,c 1,c 2 ….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: Nhooo

Enter String to find: a

String a found at position 6

Enter Input String: Nhooo

Enter String to find: b

String not found

以上是 用于实现滚动哈希的C ++程序 的全部内容, 来源链接: utcz.com/z/316395.html

回到顶部