Алгоритмы хеширования строк
Хеширование строки — это преобразование строки в число (хеш).
Хеш-функция должна быть детерминированной: одна и та же строка всегда даёт один и тот же хеш.
Одно из самых распространённых определений полиномиального хеша для строки :
Где:
Пример:
Для длинных строк хеши становятся большими, поэтому мы берём по модулю большого простого числа :
Коллизии (разные строки с одинаковым хешем) возможны, но редки при хороших параметрах.
Дано:
Найти все такие, что:
Наивно:
Хеширование:
Определим:
Следующее окно:
Связь:
Так что мы можем обновлять за .
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 {};
// хеш шаблона
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);
// последнее окно
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;
}