Hashing a string means transforming it into a number.
More formally, we choose a deterministic function that takes a string and returns some integer value called its hash. Deterministic means that the same string must always produce the same hash.
One of the most common ways to define a hash for a string is:
Solve these external problems (e.g., from Codeforces) to reinforce the lesson material:
Here:
For example, if the string consists of lowercase English letters, we may map:
'a' \to 1'b' \to 2'z' \to 26and choose or .
For long strings, the hash value can become very large, so in practice we compute everything modulo a large prime number :
Different strings may sometimes have the same hash. This is called a collision. In most competitive programming problems, collisions are rare enough that we usually ignore them, or reduce the risk further by using double hashing.
This version computes the hash directly from left to right:
This version computes the same polynomial hash in a slightly different form:
Given a string of length and a string of length , we want to find all positions
such that
A naive solution checks every position separately in time, which leads to total complexity .
We can do better using string hashing.
Let:
hashT be the hash of string ;hashS_i be the hash of the substring .Then every position such that
is a candidate occurrence of the pattern.
We can compute hashT in .
We can also compute the hash of the last substring in .
Now let us compare two neighboring substring hashes:
If we multiply hashS_{i+1} by , we shift all powers by one:
So we can reconstruct hashS_i as:
This means we can compute each substring hash from the next one in time.
Therefore, all substring hashes can be computed in total time, and the full solution works in:
const int P = 29;
const int M = 1e9 + 7;
vector<int> pw;
void init() {
pw.resize(N);
pw[0] = 1;
for (int i = 1; i < N; i++) {
pw[i] = pw[i - 1] * 1ll * P % M;
}
}
int h(string s) {
int res = 0;
for (int i = 0; i < (int)s.size(); i++) {
int x = s[i] - 'a' + 1;
res = (1ll * x * pw[i] + res) % M;
}
return res;
}
int h(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> solve(string s, string t) {
int n = s.size();
int m = t.size();
if (m > n) {
return {};
}
int hashT = 0;
for (int i = 0; i < m; i++) {
hashT = (1ll * (t[i] - 'a' + 1) * pw[i] + hashT) % M;
}
vector<int> hashS(n - m + 1, 0);
for (int i = 0; i < m; i++) {
hashS[n - m] = (hashS[n - m] +
1ll * (s[n - m + i] - 'a' + 1) * pw[i]) % M;
}
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;
}