在Rabin Karp算法中理解滚动散列与模的工作方式

Question

我很难理解滚动哈希算法是如何工作的后，哈希已通过除以素数的模数值。

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

第一个块是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。

Answer 2

@dejvuth的回答是对的--我想在做rabin时特别加上这个-karp是，有时你可能得到一个-ve模数值--在这种情况下，最好取这个模数的+ve等价物，这样检查之前是否看到相同的模数就更容易了。

例如:使用此模式，"abcdabc" -和散列函数：hash(i) = (49*S[i]+7*S[i+1]+1*S[i+2])%1123

在以下方面的成果：

"abc" -> 1046
"bcd" -> 1103
"cda" -> 33
"dab" -> 62
"abc" -> -77

"abc"结果的第二次出现是-77，它是自(-77 + 1123 = 1046)以来的1046的模等价。

PS:我现在还没有足够的“声誉”来补充这个评论。