Хеширование строк: различия между версиями
Перейти к навигации
Перейти к поиску
Ctrlalt (обсуждение | вклад) (→Ссылки) |
Ctrlalt (обсуждение | вклад) (→Ссылки) |
||
| Строка 53: | Строка 53: | ||
* [http://codeforces.com/blog/entry/4898 codeforces.com — Anti-hash test] | * [http://codeforces.com/blog/entry/4898 codeforces.com — Anti-hash test] | ||
* [http://codeforces.com/blog/entry/60445 codeforces.com — Полиномиальное хеширование + разбор интересных задач] | * [http://codeforces.com/blog/entry/60445 codeforces.com — Полиномиальное хеширование + разбор интересных задач] | ||
* [https://blog.algoprog.ru/hash-no-multiply/ Калинин П. — Про хеширование без домножения] | |||
Код: | Код: | ||
* [ | * [https://github.com/indy256/codelibrary/blob/master/cpp/strings/hashing.cpp codelibrary/cpp/strings/hashing.cpp] | ||
* [ | * [https://github.com/ADJA/algos/blob/master/Strings/Hashing.cpp algos/Strings/Hashing.cpp] | ||
Задачи: | Задачи: | ||
* [[:Категория: Задачи: Хеширование строк|Задачи: Хеширование строк]] | * [[:Категория: Задачи: Хеширование строк|Задачи: Хеширование строк]] | ||
[[Категория:Строки]] | [[Категория:Строки]] | ||
Версия от 14:21, 11 октября 2020
unsigned long long f = 31, p[100010], h[100010];
void buildHash(char s[]) {
p[0] = 1;
h[0] = s[0] - 'a' + 1;
for (int i = 1; s[i]; i++) {
p[i] = p[i - 1] * f;
h[i] = h[i - 1] + p[i] * (s[i] - 'a' + 1);
}
}
bool areEqual(int l1, int r1, int l2, int r2) {
unsigned long long h1 = h[r1] - (l1 ? h[l1 - 1] : 0);
unsigned long long h2 = h[r2] - (l2 ? h[l2 - 1] : 0);
if (l1 < l2)
h1 *= p[l2 - l1];
if (l2 < l1)
h2 *= p[l1 - l2];
return h1 == h2;
}
|
struct Hasher {
static const int SIZE = 200010;
unsigned long long f, mod, p[SIZE], h[SIZE];
Hasher(int f, int mod) : f(f), mod(mod) {
p[0] = 1;
for (int i = 1; i < SIZE; i++)
p[i] = (p[i - 1] * f) % mod;
}
void buildHash(char s[]) {
h[0] = s[0] - 'a' + 1;
for (int i = 1; s[i]; i++)
h[i] = (h[i - 1] + (p[i] * (s[i] - 'a' + 1)) % mod) % mod;
}
unsigned long long getHash(int l, int r) {
return ((h[r] - (l ? h[l - 1] : 0) + mod) % mod * p[SIZE - 1 - l]) % mod;
}
} ha(29, 1e9 + 7), hb(31, 1e9 + 9);
|
Ссылки
Теория:
- e-maxx.ru — Алгоритмы хэширования в задачах на строки
- neerc.ifmo.ru — Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа
- neerc.ifmo.ru — Поиск наибольшей общей подстроки двух строк с использованием хеширования
- habrahabr.ru — Полиномиальные хеши и их применение
- codeforces.com — Anti-hash test
- codeforces.com — Полиномиальное хеширование + разбор интересных задач
- Калинин П. — Про хеширование без домножения
Код:
Задачи: