change rolling hash

2 files changed, 24 insertions, 1 deletions

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<ll> 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));
+    }
+};
diff --git a/string/string.tex b/string/string.tex
index a09d7f8..850c661 100644
--- a/string/string.tex
+++ b/string/string.tex
@@ -16,7 +16,7 @@
 \end{algorithm}
 
 \begin{algorithm}{Rolling Hash}
-	\sourcecode{string/rollingHash.cpp}
+	\sourcecode{string/rollingHash2.cpp}
 \end{algorithm}
 
 \begin{algorithm}{Pattern Matching mit Wildcards}