了解滚动哈希如何与 Rabin Karp 算法中的模一起使用
Understanding how rolling hash works with modulus in Rabin Karp algorithm
在通过除以素数将哈希值减至模值后，我无法理解滚动哈希算法的工作原理。
考虑数字 123456 中 5 位数字的顺序。
第一个块是 12345。我存储值，在接下来的window中，6个进来1个出去。
因此新哈希将是 (12345-1*10^4)*10 + 6 = 23456。这是相当直观的。
很明显，这些数字很大，所以我们需要一个模函数来保持它们很小。假设我为此目的取 101 作为质数。
因此 12345 将减少到 23。那么，我将如何从中得出下一个 window、23456 的滚动哈希值？
您的计算方式与计算 23456 的方式相同，但始终使用模数 101。
(((23 - (10^4 mod 101))*10) mod 101 + 6) mod 101 = 24.
这是你想要的值，因为 23456 mod 101 = 24。
@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：我现在没有足够的“声望”来添加这个作为评论..
在通过除以素数将哈希值减至模值后，我无法理解滚动哈希算法的工作原理。
考虑数字 123456 中 5 位数字的顺序。
第一个块是 12345。我存储值，在接下来的window中，6个进来1个出去。
因此新哈希将是 (12345-1*10^4)*10 + 6 = 23456。这是相当直观的。
很明显，这些数字很大，所以我们需要一个模函数来保持它们很小。假设我为此目的取 101 作为质数。
因此 12345 将减少到 23。那么，我将如何从中得出下一个 window、23456 的滚动哈希值？
您的计算方式与计算 23456 的方式相同，但始终使用模数 101。
(((23 - (10^4 mod 101))*10) mod 101 + 6) mod 101 = 24.
这是你想要的值，因为 23456 mod 101 = 24。
@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：我现在没有足够的“声望”来添加这个作为评论..