1632
правки
Изменения
м
rollbackEdits.php mass rollback
Разобьем это выражение на две части:
<tex>\mathrm{hash}(s[0..j]) = (s[0] + p s[1] +...+ p^{i-1} s[i-1]) + (p^{i} s[i] +...+ p^{j-1} s[j-1] + p^{j} s[j])</tex>
Вынесем из последней скобки множитель <tex>p^{i}</tex>:
<tex>\mathrm{hash}(s[0..j]) = (s[0] + p s[1] +...+ p^{i-1} s[i-1]) + p^{i}(s[i] +...+ p^{j-i-1} s[j-1] + p^{j-i} s[j])</tex>
Выражение в первой скобке есть не что иное, как хеш подстроки <tex>s[0..i-1]</tex>, а во второй — хеш нужной нам подстроки <tex>s[i..j]</tex>. Итак, мы получили, что:
<tex>\mathrm{hash}(s[i + 1..i + m]) = (p \cdot \mathrm{hash}(s[i + 1..i + m - 1]) + s[i + m]) \bmod r</tex>.
Получается : <tex>\mathrm{hash}(s[i + 1..i + m]) = (p \cdot \mathrm{hash}(s[i..i + m - 1]) - p^{mi} s[i] + s[i + m]) \bmod r</tex>.
==Решение==
