0

我有这个 Rabin Karp 实现。现在我为滚动哈希做的唯一事情就是power*source[i]从sourceHash. power是31^target.size()-1 % mod 但我不明白为什么我们要mod在sourceHash它变成负数时添加。我尝试添加其他值，但它不起作用，它仅在我们添加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;
}
4

1 回答 1

0

当使用模运算时(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（这里%代表剩余）。

在实现 Rabin Karp 算法时，我们可能会遇到两个潜在问题：

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

为了解决这两个问题，我们可以对余数进行归一化，并且只对安全 0 .. n - 1范围内的数字进行运算。对于任意值A，我们可以放

 A = (A % n + n) % n;
于 2021-12-14T18:22:40.693 回答