From 7f0f3e7b18eda447f525b3cc0ecdf5615407ef2f Mon Sep 17 00:00:00 2001 From: MZuenni Date: Thu, 9 Feb 2023 13:52:51 +0100 Subject: improved rolling hash for ICPC --- string/rollingHashCf.cpp | 17 +++++++++++++++++ 1 file changed, 17 insertions(+) create mode 100644 string/rollingHashCf.cpp (limited to 'string/rollingHashCf.cpp') diff --git a/string/rollingHashCf.cpp b/string/rollingHashCf.cpp new file mode 100644 index 0000000..da534a1 --- /dev/null +++ b/string/rollingHashCf.cpp @@ -0,0 +1,17 @@ +// q = 29, 53, 101, 257, 1009, 65537 +// or choose q random from [sigma, m) +// m = 1500000001, 1600000009, 1700000009 +struct Hasher { + vector 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); + }} + + 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 -- cgit v1.2.3