Понимание того, как работает подвижный хеш с модулем в алгоритме Рабина Карпа

Question

У меня возникли проблемы с пониманием того, как алгоритм скользящего хэша работает после того, как хэш был уменьшен до значения модуля, делясь на простое число.

Рассмотрите последовательность из 5 цифр в цифре 123456.

Первый кусок 12345. Я сохраняю значение, в следующем окне 6 приходит и 1 выходит.

Таким образом, новый хеш будет (12345-1*10^4)*10 + 6 = 23456. Это довольно интуитивно.

Как очевидно, эти числа большие, поэтому нам нужна функция модуля, чтобы они были маленькими. Предположим, что для этой цели я принимаю 101.

Таким образом, 12345 сократится до 23. Как тогда, из этого, я получу скользящий хеш для следующего окна, 23456?

Answer 1

Вы вычисляете так же, как рассчитываете 23456, но всегда с modulo 101.

(((23 - (10^4 mod 101))*10) mod 101 + 6) mod 101 = 24. 

который является значение, которое вы хотите, потому что 23456 mod 101 = 24.