Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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";
- }
Advertisement
Add Comment
Please, Sign In to add comment