String Hashing Algorithms
Hashing a string is the transformation of a string into a number (the hash).
A hash function must be deterministic: the same string always produces the same hash.
One of the most common polynomial hash definitions for a string :
Where:
Example:
For long strings hashes become large, so we take modulo a large prime :
Collisions (different strings with same hash) are possible but rare with good parameters.
Given:
Find all such that:
Naive:
Hashing:
Define:
Next window:
Relation:
So we can update in .
const int P = 29;
const int M = 1e9 + 7;
vector<int> pw;
void init(int N) {
pw.resize(N);
pw[0] = 1;
for (int i = 1; i < N; i++) {
pw[i] = 1LL * pw[i - 1] * P % M;
}
}
int hash_string(const string& s) {
int res = 0;
for (int i = 0; i < (int)s.size(); i++) {
int x = s[i] - 'a' + 1;
res = (res + 1LL * x * pw[i]) % M;
}
return res;
}
int hash_string(const string& s) {
int res = 0;
for (int i = (int)s.size() - 1; i >= 0; i--) {
int x = s[i] - 'a' + 1;
res = (1LL * res * P + x) % M;
}
return res;
}
vector<int> find_occurrences(string s, string t) {
int n = s.size();
int m = t.size();
if (m > n) return {};
// hash of pattern
int hashT = 0;
for (int i = 0; i < m; i++) {
hashT = (hashT + 1LL * (t[i] - 'a' + 1) * pw[i]) % M;
}
vector<int> hashS(n - m + 1);
// last window
for (int i = 0; i < m; i++) {
hashS[n - m] = (hashS[n - m] +
1LL * (s[n - m + i] - 'a' + 1) * pw[i]) % M;
}
// rolling backwards
for (int i = n - m - 1; i >= 0; i--) {
hashS[i] = (s[i] - 'a' + 1);
hashS[i] = (hashS[i] + 1LL * hashS[i + 1] * P) % M;
hashS[i] = (hashS[i] - 1LL * (s[i + m] - 'a' + 1) * pw[m]) % M;
hashS[i] = (hashS[i] + M) % M;
}
vector<int> res;
for (int i = 0; i <= n - m; i++) {
if (hashS[i] == hashT)
res.push_back(i);
}
return res;
}