資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法學研究C++ 程式實現滾動雜湊
滾動雜湊是一種雜湊函式，其中輸入在遍歷輸入的視窗中進行雜湊。
Rabin-Karp 是滾動雜湊的流行應用。Rabin 和 Karp 提出的滾動雜湊函式計算一個整數值。對於一個字串，整數值是一個字串的數字值。
Rabin-Karp 字串搜尋演算法通常使用一個非常簡單的滾動雜湊函式，該函式僅使用乘法和加法 -
H=c1ak-1+c2ak-2+….+ cka0.
其中，a 是一個常數，c1、c2…ck 是輸入字元。為了操作 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
更新日期：30-Jul-2019
1 千次瀏覽
廣告