algorithm - rabin-karp 算法使用滚动哈希排除 OR

Question

我试图理解这个问题：

在下列问题中，取字符值为： A: 0 C: 1 G: 2 T: 3

在文本 GATTACA 中，子字符串 GAT 使用异或计算的哈希值为 1。子字符串 ATT 的哈希值是多少？

l google rabin-karp 使用异或，什么都没有。有人可以帮我理解吗？非常感谢您

Answer 1

我认为您不应该使用 XOR 来查找哈希值，经典方法可以提供更好的哈希质量。但是，如果您想使用滚动哈希计算哈希值，您可以执行以下操作：

hash(ATT) = hash(GAT) xor hash(G) xor hash(T). 

顺便说一句，这是0。如果你对两个相同的值进行异或，你会得到 0，所以为了摆脱第一个 G，你需要用 GAT 再次对它进行异或。

Answer 2

关于 Rabin-Karp 的东西非常好，但在这里完全无关紧要。专注于相关部分，即：

A=0, T=3使用简单的哈希函数
查找字符串的哈希值。 ATTxor

答案是A xor T xor T = A = 0。或者，如果您绝对坚持使用滚动散列函数hash(ATT) = hash(GAT) xor G xor T = 1 xor 2 xor 3 = 0。