string - 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包含术语，我都会得到相同的结果。

这是否与正在实施的算法版本（蒙特卡洛/拉斯维加斯）有关？

Answer 1

该+q术语是为了避免处理负数。

我们要txtHash永远躺在区间[0;q[里，没有这个+q也可能在]-q;0[。

这可能会导致丢失模式。例如，如果patHash = 0xdead但你计算txtHash = -q+0xdead. 这两个值在数学上是相等的mod q，但在采用 Java 时是不同的% q。