0

我试图在这里理解 Rabin-Karp 算法：http: //algs4.cs.princeton.edu/53substring/RabinKarp.java.html。

我浏览了各种文章，现在知道多项式哈希的一般形式是 C1*A^k-1+C2*A^k-2+C3*A^k-3。查看代码，我了解它们如何添加和减去字符串中的数字。

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

在这里，程序减去前导数字，乘以整个哈希，然后添加新数字。但是，当我查看计算哈希的函数时，它并没有遵循多项式哈希的一般形式。它看起来像这样：

 private long hash(String key, int M) { 
    long h = 0; 
    for (int j = 0; j < M; j++) 
        h = (R * h + key.charAt(j)) % Q; 
    return h; 
}

在这个函数中，他们将散列和基数相乘，然后加上 key.charAt()。我认为该函数会将 key.charAt() 与从 R^k-1 开始的基数相乘。然后随着 for 循环的继续，基数将除以 R 以提供多项式中的递减幂。有人可以解释一下这个函数是如何工作的，以及它是如何以我上面提到的形式生成散列的吗？谢谢！

4

1 回答 1

0

假设哈希函数需要传输 3 位数字。它看起来像： 

{digits[0]*R^2+digits[1]*R^1+digits[2]}%Q  
= {(digit[0]*R^1+digits[1])*R+digits[2]}%Q

这将使哈希函数更容易计算。

然后应用到Rabin-Karp算法，
可以看到

RM = R^2 %Q;(M=2)

当您想移动下一位进行验证时，
您需要删除最左边的一位并添加下一位。 

txtHash = {[txtHash - R^2*most_left_digit(equal charAt(i-M))]*R+next_digit(equal charAt(i))}%Q

这是一样的

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

Mod Q 每一步都防止溢出。

于 2016-06-21T13:12:59.267 回答