http://vmath.ru/vf5/ 2026-10-13T03:43:05+0300 http://vmath.ru/vf5/ http://vmath.ru/vf5/lib/tpl/vf5/images/favicon.ico text/html 2025-08-27T00:50:48+0300 Anonymous (anonymous@undisclosed.example.com) http://vmath.ru/vf5/dedup/rabin1981?rev=1756245048&do=diff text/html 2025-08-27T15:54:59+0300 Anonymous (anonymous@undisclosed.example.com) http://vmath.ru/vf5/dedup/rabinmatchhash?rev=1756299299&do=diff Хеш Рабина (matching) Пусть $$ X=(x_1,\dots,x_n) , Y=(y_1,\dots,y_m) $$ --- бинарные векторы. Проблема сопоставления строк (string matching problem)--- это проблема нахождения одного или нескольких индексов $ i $$$ X=Y_i:=(y_i,y_{i+1},\dots, y_{i+n-1}) \, . $$$ i $$\varepsilon > 0 $$ p $$$ p>\log_2\left(\frac{nm}{\varepsilon} \right) \, . \qquad {\color{Red}{ (1)} } $$$$ a(t):=x_1t^{n-1}+\dots+x_n, \ a_i(t):=y_it^{n-1}+\dots+y_{i+n-1} \quad \mbox{при} \ i \in \{1,\dots,m+n-1\} \, . $$$ a(t)\e… text/html 2025-09-13T16:57:54+0300 Anonymous (anonymous@undisclosed.example.com) http://vmath.ru/vf5/dedup/universal_hash?rev=1757771874&do=diff Универсальное хеширование Концепция универсального хеширования была предложена в . Целью является генерация случайной хеш-функции $ h $, отображающей пространство ключей$ \mathbb U $$[m]:=\{0,1,\dots, m-1\}$$ h $$ \mathbb U $$[m]$$ x $$ y $$ \mathbb U $$ h $$$ \Pr (h(x)=h(y)) \le \frac{1}{m} \, . $$$[u]:=\{0,1,\dots,u-1\} $$ [m] $$u>m>1 $$ p \ge m $$ a \ne 0 $$ b $$[p]$$$ h_{a,b}(x):= ((ax+b) \pmod{p}) \pmod{m} \, . $$$$ \Pr_{\{a,b\}\in [p]} (h_{a,b}(x)=h_{a,b}(y)) < \frac{1}{m} \, . $$$ p=31, …