Хэши

Назовем полиномиальным хэшом строки $s$ следующую величину:

$$h(s) = \displaystyle \sum_{i=0}^{|s| - 1} s_i \cdot q^{|s| - 1 - i} \pmod {p}$$

Числа $p$ и $q$ являются параметрами хэш-функции.

Смысл хэш-функции в том, что для равных строк $s_1, s_2$ $h(s_1) = h(s_2)$. Обратное, строго говоря, неверно. Но считается, что если хэши строк были равны, то строки с очень большой вероятностью тоже были равны. В рамках конспекта дальше будем считать, что нас устраивает такая большая вероятность, поэтому если хэши равны, то и строки равны.

Заметим, что просто сравнивать строки хэшами бесполезно --- алгоритм подсчета хэш-функции требует линейного времени, ровно как и сравнение строк. Но полиномиальный хэш имеет особенность, благодаря которой после $O(n)$ затрат на предподсчет можно находить хэш любой подстроки $s$.

Насчитаем префиксные хэши $h_s(i) = h(s_0\ldots s_i)$. Заметим, что при переходе $i \to i + 1$ префиксный хэш меняется понятным образом $h_s(i + 1) = h_s(i) \cdot q + s_{i + 1}$, поэтому префиксные хэши насчитываются за линейное время.

Заметим, что $h(r) = \displaystyle \sum_{i=0}^{r} s_i \cdot q^{r - i}$, $h(l - 1) = \displaystyle \sum_{i=0}^{l - 1} s_i \cdot q^{l - 1 - i}$. Если домножить $h(l - 1)$ на $q^{r - l + 1}$, то степени $q$ для всех слагаемых $s_0, \ldots s_{l - 1}$ совпадут у $h(r)$ и $h(l - 1)$. Вычитая одно из другого, получаем $$h(r) - h(l - 1)\cdot q^{r - l + 1} = \displaystyle \sum_{i=l}^r s_i \cdot q^{r - i} = h(s_l \ldots s_r)$$

Таким образом, можно за $O(1)$ сравнивать между собой любые подстроки. Разумеется, все вычисления надо делать по модулю, а равенство не гарантируется на самом деле. Тем не менее, при простом модуле $p$ нужно $O(\sqrt{p})$ объектов для попарного сравнения, чтобы у двух различных объектов совпали хэши. При этом всегда есть возможность считать несколько хэш-функций по нескольким модулям (это эквивалентно подсчету хэш-функции по одному большому модулю).

Автор конспекта: Константин Амеличев

По всем вопросам пишите в telegram @kik0s