Хеширование строк: различия между версиями
Перейти к навигации
Перейти к поиску
Ctrlalt (обсуждение | вклад) |
Ctrlalt (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
== | 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; | |||
} | |||
== Ссылки == | == Ссылки == | ||
Теория: | |||
* [http://e-maxx.ru/algo/string_hashes e-maxx.ru — Алгоритмы хэширования в задачах на строки] | * [http://e-maxx.ru/algo/string_hashes e-maxx.ru — Алгоритмы хэширования в задачах на строки] | ||
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%BE%D0%B8%D1%81%D0%BA_%D0%BF%D0%BE%D0%B4%D1%81%D1%82%D1%80%D0%BE%D0%BA%D0%B8_%D0%B2_%D1%81%D1%82%D1%80%D0%BE%D0%BA%D0%B5_%D1%81_%D0%B8%D1%81%D0%BF%D0%BE%D0%BB%D1%8C%D0%B7%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5%D0%BC_%D1%85%D0%B5%D1%88%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D1%8F._%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%A0%D0%B0%D0%B1%D0%B8%D0%BD%D0%B0-%D0%9A%D0%B0%D1%80%D0%BF%D0%B0 neerc.ifmo.ru — Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа] | * [http://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%BE%D0%B8%D1%81%D0%BA_%D0%BF%D0%BE%D0%B4%D1%81%D1%82%D1%80%D0%BE%D0%BA%D0%B8_%D0%B2_%D1%81%D1%82%D1%80%D0%BE%D0%BA%D0%B5_%D1%81_%D0%B8%D1%81%D0%BF%D0%BE%D0%BB%D1%8C%D0%B7%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5%D0%BC_%D1%85%D0%B5%D1%88%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D1%8F._%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%A0%D0%B0%D0%B1%D0%B8%D0%BD%D0%B0-%D0%9A%D0%B0%D1%80%D0%BF%D0%B0 neerc.ifmo.ru — Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа] | ||
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%BE%D0%B8%D1%81%D0%BA_%D0%BD%D0%B0%D0%B8%D0%B1%D0%BE%D0%BB%D1%8C%D1%88%D0%B5%D0%B9_%D0%BE%D0%B1%D1%89%D0%B5%D0%B9_%D0%BF%D0%BE%D0%B4%D1%81%D1%82%D1%80%D0%BE%D0%BA%D0%B8_%D0%B4%D0%B2%D1%83%D1%85_%D1%81%D1%82%D1%80%D0%BE%D0%BA_%D1%81_%D0%B8%D1%81%D0%BF%D0%BE%D0%BB%D1%8C%D0%B7%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5%D0%BC_%D1%85%D0%B5%D1%88%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D1%8F neerc.ifmo.ru — Поиск наибольшей общей подстроки двух строк с использованием хеширования] | * [http://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%BE%D0%B8%D1%81%D0%BA_%D0%BD%D0%B0%D0%B8%D0%B1%D0%BE%D0%BB%D1%8C%D1%88%D0%B5%D0%B9_%D0%BE%D0%B1%D1%89%D0%B5%D0%B9_%D0%BF%D0%BE%D0%B4%D1%81%D1%82%D1%80%D0%BE%D0%BA%D0%B8_%D0%B4%D0%B2%D1%83%D1%85_%D1%81%D1%82%D1%80%D0%BE%D0%BA_%D1%81_%D0%B8%D1%81%D0%BF%D0%BE%D0%BB%D1%8C%D0%B7%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5%D0%BC_%D1%85%D0%B5%D1%88%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D1%8F neerc.ifmo.ru — Поиск наибольшей общей подстроки двух строк с использованием хеширования] | ||
* [http://habrahabr.ru/post/142589/ habrahabr.ru — Полиномиальные хеши и их применение] | |||
* [http://codeforces.com/blog/entry/4898 codeforces.com — Anti-hash test] | |||
Код: | |||
* [http://github.com/indy256/codelibrary/blob/master/java/src/Hashing.java CodeLibrary — Hashing on strings] | * [http://github.com/indy256/codelibrary/blob/master/java/src/Hashing.java CodeLibrary — Hashing on strings] | ||
* [http://github.com/ADJA/algos/blob/master/Strings/Hashing.cpp Algos — Hashing in strings based problems] | |||
Задачи: | |||
* [[:Категория: Задачи: Хеширование строк|Задачи: Хеширование строк]] | |||
[[Категория:Строки]] | [[Категория:Строки]] | ||
Версия от 09:45, 10 августа 2015
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;
}
Ссылки
Теория:
- e-maxx.ru — Алгоритмы хэширования в задачах на строки
- neerc.ifmo.ru — Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа
- neerc.ifmo.ru — Поиск наибольшей общей подстроки двух строк с использованием хеширования
- habrahabr.ru — Полиномиальные хеши и их применение
- codeforces.com — Anti-hash test
Код:
Задачи: