字符串匹配(滚动Hash)
#include <iostream>#include <string>
#include <cstring>
#include <cmath>
const int seed = 31;
using namespace std;
long long hash(string &s)
{
long long hash_code = 0;
for(int i=0; i<s.size()-1; ++i){
hash_code = ((hash_code + s.at(i)) * seed) % __LONG_LONG_MAX__;
}
hash_code = (hash_code + s.at(s.size()-1)) % __LONG_LONG_MAX__;
return hash_code;
}
void RabinKarp(string &source, string &pattern)
{
if(source.size()<pattern.size())
{
cout << "Error" << endl;
return;
}
long long hash_pattern = hash(pattern);
long long old_hash = 0;
string begin = source.substr(0, pattern.size());
old_hash = hash(begin);
if(old_hash == hash_pattern)
cout << "begin_index: " << 0 << endl;
for(int i=1; i<=source.size()-pattern.size(); ++i)
{
old_hash = (old_hash - source.at(i-1) * pow(seed, pattern.size()-1)) * seed + source.at(i+pattern.size()-1);
if(old_hash == hash_pattern)
cout << "begin_index: " << i << endl;
}
}
int main()
{
string a, b;
cin >> a >> b;
RabinKarp(a, b);
return 0;
}
页:
[1]