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

Question

我有一个关于选择 q 和 d 的问题 in Rabin-Karp algorithm用于搜索字符串。该算法使用值 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。这里的问题是任何重复的字母都会 self 取消——不太实用——当然 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').