滚动哈希 overflow/negative 结果保护

Question

这个问题与 rolling-hash 非常相似，但是关于 overflow/negative 结果的一些细节我仍然不清楚。

我也检查了这个 Rabin-Karp implementation 并且对下面的行有问题：

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

First question:

if we always add Q, a large prime, can this result with negative number due to overflow ? If not, why not ? If yes, shouldn't this addition be done only if result is negative ?

通常选择质数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不溢出，上面的表达式就可以了。

Second question:

If, for a moment, we didn't care about negative numbers, would it be correct to write expression bellow ?

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

是的，如果 % Q 总是给出从 0 到 Q-1 的结果（例如 Python 中的结果），上面的表达式就可以了。

Third question, this part confuses me most:

Lets assume that the overflow cannot happen when we add Q. Why is there left-most % Q operation over the leading digit ?

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.

仍然可能是负面的。不是我们想要的。

滚动哈希 overflow/negative 结果保护

Rolling hash overflow/negative result protection

java

string

algorithm

rabin-karp