java - 需要帮助来了解Rabin-Karp实现中恒定时间的滚动哈希计算

我一直在尝试在Java中实现Rabin-Karp算法。我很难在恒定时间内计算滚动哈希值。我在http://algs4.cs.princeton.edu/53substring/RabinKarp.java.html找到了一个实现。我仍然无法理解这两行的工作方式。

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

我看了几篇有关模块化算术的文章，但没有一篇文章能穿透我厚厚的头骨。请给出一些指示来理解这一点。

最佳答案

这是哈希的“滚动”方面。它消除了最早的字符(txt.charAt(i-M))的贡献，并合并了最新字符(txt.charAt(i))的贡献。

哈希函数定义为:

            M-1
hash[i] = ( SUM { input[i-j] * R^j } ) % Q
            j=0

(在这里，我使用^表示“至”的力量。)

但这可以写为高效的递归实现，如下所示:

hash[i] = (txtHash*R - input[i-M]*(R^M) + input[i]) % Q

您的参考代码正在执行此操作，但是它正在使用各种技术来确保始终正确(高效)地计算结果。

因此，例如，第一个表达式中的+ Q没有数学效果，但是可以确保总和的结果始终为正(如果为负，则% Q不会达到预期的效果)。它还将计算分为多个阶段，以防止数值溢出。