Rabin-karp:滚动哈希计算为先前计算的哈希增添了庞大的质量数字

Question

我认为我从概念上理解了使用滚动哈希匹配算法的Rabinkarp模式。在此处浏览示例实现时，我发现大量素数q被添加到先前计算的滚动哈希。

。

for (int i = m; i < n; i++) {
            // Remove leading digit, add trailing digit, check for match. 
            txtHash = (txtHash + q - RM*txt.charAt(i-m) % q) % q; //Why +q here?
            txtHash = (txtHash*R + txt.charAt(i)) % q; 
            // match
            int offset = i - m + 1;
            if ((patHash == txtHash) && check(txt, offset))
                return offset;
        }

我不确定为什么需要。我可以为此获得一些帮助吗？

在我有限的测试中，无论是否包括 q术语，我都会得到相同的结果。

这是否与正在实施哪种版本的算法(Monte Carlo/Las Vegas(有关？

Answer 1

+q术语在那里避免处理负数。

我们希望txtHash始终位于间隔[0;q[中，没有此+q也可以在]-q;0[中。

这可能导致丢失模式。例如，如果patHash = 0xdead，则计算txtHash = -q+0xdead。这两个值在数学上是平等的 mod q，但与java不同的 % q。