Изменения
→Надёжность
Покажем, что при <tex>k = 10</tex>, <tex>\mathrm{hash}(S_k) = \mathrm{hash}(not S_k)</tex>. Ведь если это так, то сами по себе <tex>S_k</tex> и <tex>not S_k</tex> встретятся в б''о''льших строках много-много раз.
Разберемся, что значит <tex>\mathrm{hash}(S_k) = \mathrm{hash}(not S_k)</tex>. Можно смело взять вместо <tex>A</tex> и <tex>B</tex> нули и единицы в коэффициентах многочлена - тем самым мы просто сократим обе части на <tex>\sum_sum\limits_{i=0}^{i<2^k- 1} 65 \cdot p^i</tex>.
Что такое <tex>\mathrm{hash}(S_k) - \mathrm{hash}(not S_k)</tex>? Нетрудно сообразить, что эта величина есть: <tex>T = p^{0} - p^{1} - p^{2} + p^{3} - p^{4} + p^{5} + p^{6} - p^{7} ... \pm p^{2^k - 1}</tex>. То есть это знакопеременная сумма степеней <tex>p</tex>, где знаки чередуются по тому же правилу, что и символы в строке.
