Я следую Руководству MIT по вычислениям Карпа-Рабина , но на самом деле не следую тому, как они настраивают самый высокий множитель в скользящем га sh, чтобы избежать отрицательных значений га sh.
Наибольший множитель может быть предварительно вычислен как:
highest_multiplier = base ** (p_len - 1) % mod
Они называют это значением "magi c".
Проблема заключается в том, что при прокатке по га sh, вы можете получить отрицательное значение для вашего га sh, если волхвы c больше, чем остальные значения га sh в слайде окна.
Наибольший множитель ("Волхвы * 1025") * ") корректируется с поправочным коэффициентом:
magic = magic * (base^-1 mod p) mod p.
У меня есть два вопроса по этому поводу, а именно, является ли «самый высокий множитель» действительно единственным значением, которое нуждается в корректировке. Во-вторых, я не смог найти хороших объяснений того, как получается поправочный коэффициент.