improved rolling hash for ICPC

2 files changed, 26 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
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<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);
+	}}
+
+	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