Струна Cormen, соответствующая Рабину-Карпу

Ваш второй вопрос, похоже, касается модульной арифметики с числами -ve. Один из способов представить это так: работая по модулю М, вы можете добавлять или вычитать М столько, сколько хотите, поскольку М эквивалентно 0 по модулю М. Таким образом, мы имеем (7-3.3).10 + 2 (мод 13) = -2,10 + 2 = -18 = 13 + 13 - 18 = 8 по модулю 13

Ваш первый вопрос менее ясен для меня, но позвольте мне рассмотреть его подробно. Когда символ впервые появляется в текстовом окне, он просто добавляется. Затем он перемещается по текстовому окну, и, наконец, мы хотим удалить всю память о нем, чтобы после выхода из текстового окна он не влиял на хэш-значение.

Сначала мы видим символ x, и прибавляем его к хэш-значению до сих пор, таким образом, мы получаем h.d + x. Когда мы видим следующий символ, мы умножаем его на d (и делаем другие вещи, которые я пытаюсь объяснить), а затем добавляем новый символ — скажем, y. Итак, мы получаем ... + x*d + y. Следующий шаг дает нам ... + x*d*d + y*d + z. Когда мы собираемся избавиться от символа, у нас есть хеш-значение x*d^(m-1) + ...., где .... зависит только от символов после x. Таким образом, мы можем удалить влияние x на хеш-значение, вычитая x*d^(m-1) перед умножением на d.