
Untitled
By: a guest on
Aug 8th, 2012 | syntax:
None | size: 0.71 KB | hits: 6 | expires: Never
Trouble with rolling hash implementation
int MUL = 37;
int MOD = 9999991;
for(int i = 1 , pwr = 1 ; i < plen ; i++) pwr = (pwr * MUL) % MOD;
long long hash = number[0];
long long revHash = number[plen - 1];
for(int i = 1 ; i < plen ; i++)
{
hash = (MUL*hash + number[i])%MOD;
revHash = (revHash*MUL + number[plen - i - 1])%MOD;
}
cout << hash << " " << revHash <<"n";
int cnt = (hash == revHash);
for(int i = plen ; i < numbers ; i++)
{
hash = (hash + (MOD - pwr)*number[i - plen])%MOD;
hash = (hash*MUL + number[i])%MOD;
revHash = ((revHash + MOD - number[i - plen]))%MOD;
revHash = (revHash + pwr*number[i])%MOD;
cnt += (hash == revHash);
cout << hash << " " << revHash << "n";
}