Изменения

Обозначим за <tex>S_k</tex> строку <tex>S</tex> для фиксированного <tex>k</tex> , а за <tex>not S_kS'_k</tex> инвертированную строку после замены <tex>AS</tex> на <tex>B</tex> и наоборот.

Покажем, что при <tex>k = 10</tex>, <tex>\mathrm{hash}(S_k) = \mathrm{hash}(not S_kS'_k)</tex>. Ведь если это так, то сами по себе <tex>S_k</tex> и <tex>not S_kS'_k</tex> встретятся в б''о''льших строках много-много раз.

Разберемся, что значит <tex>\mathrm{hash}(S_k) = \mathrm{hash}(not S_kS'_k)</tex>. Можно смело взять вместо <tex>A</tex> и <tex>B</tex> заменить коды символов на нули и единицы в коэффициентах многочлена - тем самым мы просто сократим обе части на <tex>\sum\limits_{i=0}^{2^k - 1} 65 \cdot p^i</tex>.

Что такое <tex>\mathrm{hash}(S_k) - \mathrm{hash}(not S_kS'_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>, где знаки чередуются по тому же правилу, что и символы в строке.