string - 了解滚动哈希如何与 Rabin Karp 算法中的模一起使用

Question

在通过除以质数将哈希值减少为模值后，我无法理解滚动哈希算法的工作原理。

考虑数字 123456 中的 5 位数字序列。

第一个 block 是 12345。我存储值，在下一个窗口中，6 进来，1 出去。

所以新的哈希值将是 (12345-1*10^4)*10 + 6 = 23456。这是相当直观的。

很明显，这些数字很大，所以我们需要一个模函数来保持它们很小。假设我为此目的将 101 作为质数。

因此 12345 将减少到 23。那么，如何从中导出下一个窗口 23456 的滚动散列？

Answer 1

计算方法与计算 23456 的方法相同，但始终使用模 101。

(((23 - (10^4 mod 101))*10) mod 101 + 6) mod 101 = 24.

这是您想要的值，因为 23456 mod 101 = 24。