Защита от переполнения хэша / защита от отрицательных результатов

Question

Этот вопрос очень похож на roll-hash , но есть некоторые особенности относительно переполнения / отрицательного результата, которые мне до сих пор не ясны.

Я также проверил этоРабин-Карп реализация и имеет проблемы со строкой ниже:

txtHash = (txtHash + Q - RM*txt.charAt(i-M) % Q) % Q;

Я понимаю, что следующее выражение может дать отрицательный результат:

txtHash - RM*txt.charAt(i-M)

Первый вопрос :

• Если мы всегда добавляем Q, большое простое число, может ли это привести к отрицательному числу из-за переполнения?
  • Если нет, то почему бы и нет?Если да, то не следует ли сделать это добавление только при отрицательном результате?

Второй вопрос :

Если дляв тот момент, когда мы не заботились об отрицательных числах, было бы правильно написать выражение ниже?

txtHash = (txtHash - RM*txt.charAt(i-M)) % Q;

Третий вопрос , эта часть меня больше всего смущает:

Предположим, что переполнение не может произойти, когда мы добавляем Q. Почему самая верхняя операция% Q над первой цифрой?

txtHash = (txtHash + Q - RM*txt.charAt(i-M) % Q ) % Q;

Я прочитал ответ, который связал, и согласно ответу Aneeshи если я правильно понял, приведенные ниже выражения должны быть похожи:

hash = hash - ((5 % p)*(10^2 %p) %p)

txtHash = (txtHash + Q - RM*txt.charAt(i-M) % Q) % Q;

Но я не понимаю, почему они похожи, потому что в примере с хешем% p не рассчитывается для предыдущего значения хеша, однако для txtHashмы также вычисляем% Q по предыдущему хешу.

Answer 1

Первый вопрос:

Если мы всегда добавляем Q, большое простое число, может ли это привести к отрицательному числу из-за переполнения?Если нет, то почему?Если да, то не следует ли сделать это добавление только в том случае, если результат отрицательный?

Простое число Q обычно выбирается таким образом, чтобы 2Q все еще не переполняло тип.

Теперь давайтесм.

• txtHash от 0 до Q - 1.
• RM*txt.charAt(i-M) большой.
• RM*txt.charAt(i-M) % Q от 0 до Q - 1.
• txtHash - RM*txt.charAt(i-M) % Q от - (Q - 1) до Q - 1.
• txtHash + Q - RM*txt.charAt(i-M) % Q - от 1 до 2Q - 1.

Такдо тех пор, пока 2Q - 1 не переполняется, вышеприведенное выражение в порядке.

Второй вопрос:

Если на мгновение нас не волновали отрицательные числа,Было бы правильно написать выражение ниже?

txtHash = (txtHash - RM*txt.charAt(i-M)) % Q;

Да, если бы % Q всегда давал результат от 0 до Q-1 (как это происходит в Pythonнапример), вышеприведенное выражение было бы хорошо.

Третий вопрос, эта часть меня больше всего смущает:

Предположим, что переполнение не может произойти, когда мы добавляем Q. Почемукрайняя левая операция% Q над первой цифрой?

txtHash = (txtHash + Q - RM*txt.charAt(i-M) % Q ) % Q;

Предположим, мы удалили самый левый % Q.Затем давайте оценим снова:

• txtHash от 0 до Q - 1.
• RM*txt.charAt(i-M) большой.
• Насколько большой?От 0 до (Q - 1) * CharCode.
• txtHash - RM*txt.charAt(i-M) от - (Q - 1) * (CharCode - 1) до Q - 1.
• txtHash + Q - RM*txt.charAt(i-M) от- (Q - 1) * (CharCode - 2) до 2Q - 1.

Все еще возможно отрицательно.Не то, что мы хотели.