algorithm - 如何在 Rabin-Karp 算法中选择模值？

Question

我有一个关于在 Rabin-Karp 算法中选择q和d 来搜索字符串的问题。该算法使用值q作为模数和d作为散列函数。

如果我选择q作为 2 的幂数并且 d=q-1 或 d=q+1

• 这些选择如何影响虚假命中？

• 在 d=q+1 和 d=q-1 的情况下，哪些模式会确保虚假命中？

Answer 1

X mod (2^n +1) 可以描述为交替的和/差，例如

X= 0x11223344, n=8, X mod 257 == 0x44 - 0x33 + 0x22 - 0x11 mod 257。这里的问题是任何重复的字母都会自行取消——不太实用——当然n不必是8.

X mod (2^n -1) 将是所有 n 位模式的总和，例如

X= 0x11223344, n=8, X mod 255 ==( 0x44 + 0x33 +0x22 +0x11 ) mod 255

这里的问题是切换字节会自行取消：Hash('ab') = Hash('ba')。