diff options
Diffstat (limited to 'string/rollingHash.cpp')
| -rw-r--r-- | string/rollingHash.cpp | 19 |
1 files changed, 9 insertions, 10 deletions
diff --git a/string/rollingHash.cpp b/string/rollingHash.cpp index da534a1..ad9e7cd 100644 --- a/string/rollingHash.cpp +++ b/string/rollingHash.cpp @@ -1,17 +1,16 @@ -// q = 29, 53, 101, 257, 1009, 65537 -// or choose q random from [sigma, m) +// q = 29, 101, 257, 65537, 100003, 1000033 (or random) // m = 1500000001, 1600000009, 1700000009 +// always compare hash and length of hashed range! +template<ll M, ll Q> struct Hasher { vector<ll> power = {1}, pref = {0}; - ll m, q; char c; - Hasher(const string& s, ll m, ll q, char c) : - m(m), q(q), c(c) { - for (char x : s) { - power.push_back(power.back() * q % m); - pref.push_back((pref.back() * q % m + (x - c)) % m); + Hasher(const string& s) { + for (auto x : s) { + power.push_back(power.back() * Q % M); + pref.push_back((pref.back() * Q % M + x) % M); }} - ll hash(int l, int r) { // Berechnet hash(s[l..r)). - return (pref[r] - power[r-l] * pref[l] % m + m) % m; + ll hash(int l, int r) { // Berechnet hash(s[l..r)). + return (pref[r] - power[r-l] * pref[l] % M + M) % M; } };
\ No newline at end of file |