Хеширование строк - История изменений

Ctrlalt в 01:48, 18 декабря 2025

2025-12-18T01:48:21Z

← Предыдущая версия		Версия от 01:48, 18 декабря 2025
Строка 73:		Строка 73:
	};		};

	{\| width="100%"		<!--{\| width="100%"
	\| width=50% \|		\| width=50% \|
	h<sub>i</sub> = s<sub>0</sub> + s<sub>1</sub>x + s<sub>2</sub>x<sup>2</sup> + ... + s<sub>n - 1</sub>x<sup>n - 1</sup>.		h<sub>i</sub> = s<sub>0</sub> + s<sub>1</sub>x + s<sub>2</sub>x<sup>2</sup> + ... + s<sub>n - 1</sub>x<sup>n - 1</sup>.
Строка 141:		Строка 141:
	}		}
	};		};
	\|}		\|}-->

	== Ссылки ==		== Ссылки ==

Ctrlalt в 01:28, 18 декабря 2025

2025-12-18T01:28:59Z

@@ Строка 2: / Строка 2: @@
   struct Hasher {
-      long long x, mod;
+      long long mod;
       vector<long long> p, h;
-      Hasher(const string &s, long long x = 31, long long mod = 1e9 + 7) : x(x), mod(mod) {
+      Hasher(const string &s, long long factor = 31, long long mod = 1e9 + 7) : mod(mod) {
-          p.resize(s.size());
+          p.push_back(1);
-          h.resize(s.size());
+          for (int i = 1; i < s.size(); i++)
-         p[0] = 1;
+          h.push_back(s[0] - 'a' + 1);
-          h[0] = s[0] - 'a' + 1;
+          for (int i = 1; i < s.size(); i++)
+              h.push_back((h[i - 1] * factor % mod + s[i] - 'a' + 1) % mod);
+      }
@@ Строка 33: / Строка 30: @@
       pair<long long, long long> getHash(int l, int r) {
           return { h1.getHash(l, r), h2.getHash(l, r) };
+      }
   };

Ctrlalt в 15:33, 16 декабря 2024

2024-12-16T15:33:33Z

@@ Строка 23: / Строка 23: @@
               res = (res - p[r - l + 1] * h[l - 1] % mod + mod) % mod;
           return res;
+      }
   };

Ctrlalt в 00:32, 5 марта 2024

2024-03-05T00:32:11Z

← Предыдущая версия		Версия от 00:32, 5 марта 2024
Строка 2:		Строка 2:

	struct Hasher {		struct Hasher {
	long long x ~~= 31~~, mod ~~= 1e9 + 7~~;		long long x, mod;
	vector<long long> p, h;		vector<long long> p, h;

	Hasher(const string &s) {		Hasher(const string &s, long long x = 31, long long mod = 1e9 + 7) : x(x), mod(mod) {
	p.resize(s.size());		p.resize(s.size());
	h.resize(s.size());		h.resize(s.size());

Ctrlalt: /* Ссылки */

2021-12-07T09:52:12Z

Ссылки

← Предыдущая версия		Версия от 09:52, 7 декабря 2021
Строка 101:		Строка 101:
	* [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 — Поиск наибольшей общей подстроки двух строк с использованием хеширования]
			* [https://ru.algorithmica.org/cs/hashing/polynomial/ ru.algorithmica.org — Полиномиальное хеширование]
	* [http://habrahabr.ru/post/142589/ habrahabr.ru — Полиномиальные хеши и их применение]		* [http://habrahabr.ru/post/142589/ habrahabr.ru — Полиномиальные хеши и их применение]
	* [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://blog.algoprog.ru/hash-no-multiply/ Калинин П. — Про хеширование без домножения]
			* [https://usaco.guide/gold/string-hashing?lang=cpp usaco.guide — String Hashing]
	Код:		Код:
	* [https://github.com/indy256/codelibrary/blob/master/cpp/strings/hashing.cpp codelibrary/cpp/strings/hashing.cpp]		* [https://github.com/indy256/codelibrary/blob/master/cpp/strings/hashing.cpp codelibrary/cpp/strings/hashing.cpp]

Ctrlalt в 01:41, 7 декабря 2021

2021-12-07T01:41:31Z

← Предыдущая версия		Версия от 01:41, 7 декабря 2021
Строка 1:		Строка 1:
	~~unsigned~~ long long f = 31, p~~[100010]~~, h~~[100010]~~;		h<sub>i</sub> = s<sub>0</sub>x<sup>n - 1</sup> + s<sub>1</sub>x<sup>n - 2</sup> + ... + s<sub>n - 2</sub>x + s<sub>n - 1</sub>.

			struct Hasher {
			long long x = 31, mod = 1e9 + 7;
			vector<long long> p, h;

	~~void buildHash~~(~~char~~ s[]) {		Hasher(const string &s) {
	p[0] = 1;		p.resize(s.size());
	h[0] = s[0] - 'a' + 1;		h.resize(s.size());
	for (int i = 1; s~~[i]~~; i++) {
	p[i] = p[i - 1] * f;		p[0] = 1;
	h[i] = h[i - 1] + ~~p[i] * (~~s[i] - 'a' + 1);		h[0] = s[0] - 'a' + 1;

			for (int i = 1; i < s.size(); i++) {
			p[i] = p[i - 1] * x % mod;
			h[i] = (h[i - 1] * x % mod + s[i] - 'a' + 1) % mod;
			}
	}		}
	}

	~~bool areEqual~~(int ~~l1, int r1, int l2~~, int r2) {		long long getHash(int l, int r) {
	~~unsigned~~ long long h1 = h[r1] - (~~l1 ? h[l1 - 1] : 0~~);		long long res = h[r];
	~~unsigned long long h2~~ = ~~h[r2]~~ - ~~(l2 ? h~~[l2 - 1] ~~: 0);~~		if (l)
	~~if (l1 < l2)~~		res = (res - p[r - l + 1] * h[l - 1] % mod + mod) % mod;
	h1 *~~= p~~[l2 - l1];		return res;
	~~if (l2 < l1)~~		}
	~~h2 *= p[l1 - l2]~~;		};
	~~return h1 == h2;~~
	}

	{\| width="100%"		{\| width="100%"
	\| width=50% \|		\| width=50% \|
			h<sub>i</sub> = s<sub>0</sub> + s<sub>1</sub>x + s<sub>2</sub>x<sup>2</sup> + ... + s<sub>n - 1</sub>x<sup>n - 1</sup>.

			Для выравнивания хеши различных подстрок домножаются на x<sup>n - 1 - L</sup>.

	struct Hasher {		struct Hasher {
	long long f = 31, mod = 1e9 + 7;		long long x = 31, mod = 1e9 + 7;
	vector<long long> p, h;		vector<long long> p, h;

	Hasher(string &s) {		Hasher(const string &s) {
	p.resize(s.size());		p.resize(s.size());
	h.resize(s.size());		h.resize(s.size());
Строка 34:		Строка 44:

	for (int i = 1; i < s.size(); i++) {		for (int i = 1; i < s.size(); i++) {
	p[i] = (p[i - 1] * f) % mod;		p[i] = p[i - 1] * x % mod;
	h[i] = (h[i - 1] + (p[i] * (s[i] - 'a' + 1)) % mod) % mod;		h[i] = (h[i - 1] + p[i] * (s[i] - 'a' + 1) % mod) % mod;
	}		}
	}		}
Строка 43:		Строка 53:
	if (l)		if (l)
	res = (res - h[l - 1] + mod) % mod;		res = (res - h[l - 1] + mod) % mod;
	res = (res * p[p.size() - 1 - l]) % mod;		res = res * p[p.size() - 1 - l] % mod;
	return res;		return res;
	}		}
	};		};

			Этот способ непригоден для сравнения участков двух строк разной длины. В данном случае хеш более левого участка следует домножать на x<sup>\|L1 - L2\|</sup>.

	\| width="10px" \|		\| width="10px" \|
	\| width=50% \|		\| width=50% \|
			h<sub>i</sub> = s<sub>0</sub> + s<sub>1</sub>x + s<sub>2</sub>x<sup>2</sup> + ... + s<sub>n - 1</sub>x<sup>n - 1</sup>.

			Для выравнивания хеши различных подстрок домножаются на (x<sup>-1</sup>)<sup>L</sup>.

	struct Hasher {		struct Hasher {
	long long f = 31, {{Changed\|1=fi = 129032259,}} mod = 1e9 + 7;		long long x = 31, {{Changed\|1=xi = 129032259,}} mod = 1e9 + 7;
	vector<long long> p, {{Changed\|pi,}} h;		vector<long long> p, {{Changed\|pi,}} h;

Строка 64:		Строка 79:

	for (int i = 1; i < s.size(); i++) {		for (int i = 1; i < s.size(); i++) {
	p[i] = (p[i - 1] * f) % mod;		p[i] = p[i - 1] * x % mod;
	{{Changed\|1=pi[i] = (pi[i - 1] * ~~fi)~~ % mod;}}		{{Changed\|1=pi[i] = pi[i - 1] * xi % mod;}}
	h[i] = (h[i - 1] + (p[i] * (s[i] - 'a' + 1)) % mod) % mod;		h[i] = (h[i - 1] + p[i] * (s[i] - 'a' + 1) % mod) % mod;
	}		}
	}		}

Ctrlalt в 17:17, 11 сентября 2021

2021-09-11T17:17:57Z

← Предыдущая версия		Версия от 17:17, 11 сентября 2021
Строка 41:		Строка 41:
	long long getHash(int l, int r) {		long long getHash(int l, int r) {
	long long res = h[r];		long long res = h[r];
	if (l) {		if (l)
	res = (res - h[l - 1] + mod) % mod;		res = (res - h[l - 1] + mod) % mod;
	res = (res * p[p.size() - 1 - l]) % mod;		res = (res * p[p.size() - 1 - l]) % mod;
	}
	return res;		return res;
	}		}
Строка 75:		Строка 74:
	if (l) {		if (l) {
	res = (res - h[l - 1] + mod) % mod;		res = (res - h[l - 1] + mod) % mod;
	res = (res * ~~{{Changed\|~~pi[l]}}) % mod;		{{Changed\|1=res = (res * pi[l]) % mod}};
	}		}
	return res;		return res;

Ctrlalt в 17:01, 11 сентября 2021

2021-09-11T17:01:02Z

@@ Строка 1: / Строка 1: @@
   unsigned long long f = 31, p[100010], h[100010];
@@ Строка 21: / Строка 19: @@
       return h1 == h2;
+  }
 | width="10px" | &nbsp;
-| width="50%"  |
+| width=50% |
   struct Hasher {
-    static const int SIZE = 200010;
+     long long f = 31, {{Changed|1=fi = 129032259,}} mod = 1e9 + 7;
-    unsigned long long f, mod, p[SIZE], h[SIZE];
+     vector<long long> p, {{Changed|pi,}} h;
-    Hasher(int f, int mod) : f(f), mod(mod) {
+     Hasher(const string &s) {
-        p[0] = 1;
+         p.resize(s.size());
-        for (int i = 1; i < SIZE; i++)
+         {{Changed|pi.resize(s.size());}}
-            p[i] = (p[i - 1] * f) % mod;
+         h.resize(s.size());
-    void buildHash(char s[]) {
+         p[0] = {{Changed|1=pi[0] = }} 1;
-        h[0] = s[0] - 'a' + 1;
+         h[0] = s[0] - 'a' + 1;
-    unsigned long long getHash(int l, int r) {
+         for (int i = 1; i < s.size(); i++) {
-        return ((h[r] - (l ? h[l - 1] : 0) + mod) % mod * p[SIZE - 1 - l]) % mod;
+             p[i] = (p[i - 1] * f) % mod;
+             {{Changed|1=pi[i] = (pi[i - 1] * fi) % mod;}}
-  } ha(29, 1e9 + 7), hb(31, 1e9 + 9);
+             h[i] = (h[i - 1] + (p[i] * (s[i] - 'a' + 1)) % mod) % mod;
 |}

Ctrlalt: /* Ссылки */

2020-10-11T14:21:57Z

Ссылки

← Предыдущая версия		Версия от 14:21, 11 октября 2020
Строка 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/ Калинин П. — Про хеширование без домножения]
	Код:		Код:
	* [~~http~~://github.com/indy256/codelibrary/blob/master/~~java~~/~~src~~/~~Hashing~~.~~java CodeLibrary — Hashing on~~ strings]		* [https://github.com/indy256/codelibrary/blob/master/cpp/strings/hashing.cpp codelibrary/cpp/strings/hashing.cpp]
	* [~~http~~://github.com/ADJA/algos/blob/master/Strings/Hashing.cpp ~~Algos —~~ Hashing ~~in strings based problems~~]		* [https://github.com/ADJA/algos/blob/master/Strings/Hashing.cpp algos/Strings/Hashing.cpp]
	Задачи:		Задачи:
	* [[:Категория: Задачи: Хеширование строк\|Задачи: Хеширование строк]]		* [[:Категория: Задачи: Хеширование строк\|Задачи: Хеширование строк]]

	[[Категория:Строки]]		[[Категория:Строки]]

Ctrlalt: /* Ссылки */

2018-07-09T08:23:27Z

Ссылки

← Предыдущая версия		Версия от 08:23, 9 июля 2018
Строка 52:		Строка 52:
	* [http://habrahabr.ru/post/142589/ habrahabr.ru — Полиномиальные хеши и их применение]		* [http://habrahabr.ru/post/142589/ habrahabr.ru — Полиномиальные хеши и их применение]
	* [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://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]