在通过除以素数将散列减少为模值后，我无法理解滚动散列算法的工作原理。
考虑数字中的 5 位数字序列123456。
第一个块是12345. 我存储值，在下一个窗口中，6 进来，1 出去。
所以新的哈希将是(12345-1*10^4)*10 + 6 = 23456. 这是相当直观的。
很明显，这些数字很大，所以我们需要一个模函数来保持它们很小。假设我101为此目的取素数。
所以12345会减少到23。那么，如何从中得出下一个窗口的滚动哈希23456？
问问题
1766 次
2 回答
6
您以与计算相同的方式计算它23456，但始终使用模数101。
(((23 - (10^4 mod 101))*10) mod 101 + 6) mod 101 = 24.
这是您想要的值，因为23456 mod 101 = 24.
于 2016-04-23T18:03:46.160 回答
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是模等效于1046因为(-77 + 1123 = 1046)
PS：我现在没有足够的“声誉”来添加这个作为评论..
于 2020-07-22T20:35:36.890 回答