Rabin Karp 算法负散列

Question

我有这个 Rabin Karp 实现。现在，我为滚动哈希所做的唯一事情就是从 sourceHash 中减去 power*source[i]。 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;
}

Answer 1

当使用模运算 (mod n) 时，我们只有 n distinct 个数字：0, 1, 2, ..., n - 1。 0 .. n - 1 的 out 中的所有其他数字等于 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 算法时，我们可能会遇到两个潜在问题：

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

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

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

Rabin Karp 算法负散列

Rabin Karp Algorithm Negative Hash

c++

algorithm

rabin-karp