algorithm - 如何使用修改后的 Rabin-Karp 为字母分配数字以进行字谜搜索

Question

我必须为字母 a、b、c、d...z 分配数字，这样对于给定的字符串和所有字谜搜索，我们可以使用散列搜索在 o(n) 中进行。散列函数应该是 s[0]+s[1]+s[2]..s[n-1]。Anagram 与位置无关，因此不需要像 Rabin-Karp 那样乘以位置幂。

Answer 1

选择一些方便的素数模 p（可能是 2 ³¹ - 1），然后将每个字母映射到介于 0 和 p-1 之间的随机数。可以证明，假设每个单词的每个字母少于 p，则两个单词之间发生虚假碰撞的概率为 1/p。