java - 滚动哈希溢出/负结果保护

这个问题与rolling-hash非常相似，但是有些关于溢出/负结果的细节我仍然不清楚。
我也检查过这个rabin karpimplementation并且对下面的行有问题：

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;

但是我不明白为什么它们是相似的，因为在hash的例子中，前一个hash值不计算%p，但是对于txthash，我们也计算前一个hash的%q。

最佳答案

第一个问题：
如果我们总是加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到2季度-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）*字符码。
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。
可能还是阴性。
不是我们想要的。

关于java - 滚动哈希溢出/负结果保护，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/53729966/