Хеширование строк: различия между версиями
Перейти к навигации
Перейти к поиску
Ctrlalt (обсуждение | вклад) Нет описания правки |
Ctrlalt (обсуждение | вклад) Нет описания правки |
||
Строка 19: | Строка 19: | ||
return h1 == h2; | return h1 == h2; | ||
} | } | ||
struct Hasher { | |||
unsigned long long f, mod, p[210], h[210]; | |||
Hasher() { | |||
f = 31; | |||
mod = 1e9 + 7; | |||
p[0] = 1; | |||
for (int i = 1; i < 210; 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] + ((s[i] - 'a' + 1) * p[i]) % mod) % mod; | |||
} | |||
unsigned long long getHash(int l, int r) { | |||
return ((h[r] - (l ? h[l - 1] : 0) + mod) % mod * p[209 - l]) % mod; | |||
} | |||
} hasher; | |||
== Ссылки == | == Ссылки == |
Версия от 19:32, 27 мая 2018
unsigned long long X = 31, p[100010], h[100010]; void buildHash(char *s) { p[0] = 1; h[0] = s[0] - 'a'; for (int i = 1; s[i]; i++) { p[i] = p[i - 1] * X; h[i] = h[i - 1] + p[i] * (s[i] - 'a'); } } 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 { unsigned long long f, mod, p[210], h[210]; Hasher() { f = 31; mod = 1e9 + 7; p[0] = 1; for (int i = 1; i < 210; 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] + ((s[i] - 'a' + 1) * p[i]) % mod) % mod; } unsigned long long getHash(int l, int r) { return ((h[r] - (l ? h[l - 1] : 0) + mod) % mod * p[209 - l]) % mod; } } hasher;
Ссылки
Теория:
- e-maxx.ru — Алгоритмы хэширования в задачах на строки
- neerc.ifmo.ru — Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа
- neerc.ifmo.ru — Поиск наибольшей общей подстроки двух строк с использованием хеширования
- habrahabr.ru — Полиномиальные хеши и их применение
- codeforces.com — Anti-hash test
Код:
Задачи: