拉宾卡普算法负哈希

Question

我有这个Rabin Karp实现。现在我为滚动哈希所做的唯一一件事就是从sourceHash中减去power*source[i]。power31^target.size()-1 % mod但我不明白为什么当sourceHash变成负数时，我们要在中添加mod。我尝试添加其他值，但它不起作用，并且仅在我们添加mod时才有效。这是为什么呢？我们添加mod而不是其他任何东西(例如随机大数)是否有特定原因。

int rbk(string source, string target){
int m = target.size();
int n = source.size();
int mod = 128;
int prime = 11;
int power = 1;
int targetHash = 0, sourceHash = 0;
for(int i = 0; i < m - 1; i++){
power =(power*prime) % mod;
}
for(int i = 0; i < target.size(); i++){
sourceHash = (sourceHash*prime + source[i]) % mod;
targetHash = (targetHash*prime + target[i]) % mod;
}

for(int i = 0; i < n-m+1; i++){
if(targetHash == sourceHash){
bool flag = true;
for(int j = 0; j < m; j++){
if(source[i+j] != target[j]){
flag = false;
break;
}
}
if(flag){
return 1;
}
}

if(i < n-m){
sourceHash = (prime*(sourceHash - source[i]*power) + source[i+m]) % mod;
if(sourceHash < 0){
sourceHash += mod;
}
}
}
return -1;
}

Answer 1

当使用模算术时(mod n)我们只有n个不同的数字：0, 1, 2, ..., n - 1。 所有其他0 .. n - 1等于0 .. n - 1中的某个数字：

-n     ~ 0
-n + 1 ~ 1
-n + 2 ~ 2
...
-2     ~ n - 2
-1     ~ n - 1

或

n     ~ 0
n + 1 ~ 1
n + 2 ~ 2
...
2 * n     ~ 0
2 * n + 1 ~ 0

在一般情况下，A ~ B当且仅当(A - B) % n = 0(这里%代表余数)。

在实现拉宾卡普算法时，我们可能会遇到两个潜在的问题：

1. 哈希可能太大，我们可能会面临整数溢出
2. 负余数可以在不同的编译器上以不同的方式实现：-5 % 3 == -2 == 1

为了处理这两个问题，我们可以规范化余数，并仅使用安全0 .. n - 1范围内的数字进行操作。 对于任意值A我们可以放置

A = (A % n + n) % n;