字符串匹配(滚动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;
}