From e5c8b1f433cad341b2c8f02fa444604b20fe694d Mon Sep 17 00:00:00 2001 From: Noobie99 Date: Wed, 22 Nov 2023 12:16:41 +0100 Subject: change rolling hash --- string/rollingHash2.cpp | 23 +++++++++++++++++++++++ 1 file changed, 23 insertions(+) create mode 100644 string/rollingHash2.cpp (limited to 'string/rollingHash2.cpp') diff --git a/string/rollingHash2.cpp b/string/rollingHash2.cpp new file mode 100644 index 0000000..7660842 --- /dev/null +++ b/string/rollingHash2.cpp @@ -0,0 +1,23 @@ +// M = 1.7e9 + 9, 1e18L + 9, 2.2e18L + 7 +struct Hash { + static constexpr ll M = 3.1e18L + 7; + static constexpr ll Q = 2e18L + 43; // Random number in [SIGMA+1, M) + vector pref = {0}, power = {1}; + + Hash(const string& s) { + for (auto c : s) { + pref.push_back((mul(pref.back(), Q) + c) % M); + power.push_back(mul(power.back(), Q)); + }} + + ll operator()(int l, int r) { + return (pref[r] - mul(power[r-l], pref[l]) + M) % M; + } + + // can also just use __int128 multiplication and mod (slower) + using ull = uint64_t; + static ll mul(ull a, ull b) { // 0 < a,b <= M <= 7.268 * 10^18 + ll ans = (a * b - M * ull(1.L / M * a * b)); + return ans + M * ((ans < 0) - (ans >= M)); + } +}; -- cgit v1.2.3