304
правки
Изменения
Нет описания правки
==Метод хеширования==
Для решения задачи удобно использовать полиномиальный хеш, так его легко пересчитывать: <tex>hash(s[1..n]) = (p^{n - 1} s[1] + ... + p^{0} s[n])\bmod r</tex>, где <tex>p</tex> {{---}} это некоторое простое число, а <tex>r</tex> {{---}} некоторое большое число, чтобы было меньше коллизий (обычно берётся <tex>2^{32}</tex> или <tex>2^{64}</tex>, чтобы модуль брался автоматически при переполнении типов). Стоит обратить внимание, что если 2 строчки имеют одинаковый хэш, то они в большинстве таких случаев равны.
При удалении первого символа строки и добавлении символа в конец считать хеш новой строки при помощи хеша изначальной строки возможно за <tex>O(1)</tex>:
<tex>hash(s[i + 1..i + m - 1]) = (hash(s[i..i + m - 1]) - p^{m - 1} s[i]) mod \bmod r</tex>.
<tex>hash(s[i + 1..i + m]) = (p \cdot hash(s[i + 1..i + m - 1]) + s[i + m]) mod \bmod r</tex>.
Получается : <tex>hash(s[i + 1..i + m]) = (p \cdot hash(s[i..i + m - 1]) - p^{m} s[i] + s[i + m]) mod \bmod r</tex>.
Следует учесть, что при получении отрицательного значения необходимо прибавить <tex>r</tex>.
