如何使用修改后的 Rabin-Karp 将数字分配给字母以进行字谜搜索
How to assign numbers to letters for anagram search using modified Rabin-Karp
我必须将数字分配给字母 a、b、c、d...z，以便对于给定的字符串和所有字谜搜索，我们可以使用散列搜索在 o(n) 内完成。哈希函数应该是 s[0]+s[1]+s[2]..s[n-1]。 Anagram 与位置无关，因此无需像 Rabin-Karp 那样乘以位置幂。
选择一些方便的质数模数 p（可能是 231 − 1），然后将每个字母映射到 0 和 p−1 之间的随机数（包括 0 和 p−1）。可以证明，假设每个单词的每个字母少于p，则两个单词之间发生虚假碰撞的概率为1/p。
我必须将数字分配给字母 a、b、c、d...z，以便对于给定的字符串和所有字谜搜索，我们可以使用散列搜索在 o(n) 内完成。哈希函数应该是 s[0]+s[1]+s[2]..s[n-1]。 Anagram 与位置无关，因此无需像 Rabin-Karp 那样乘以位置幂。
选择一些方便的质数模数 p（可能是 231 − 1），然后将每个字母映射到 0 和 p−1 之间的随机数（包括 0 和 p−1）。可以证明，假设每个单词的每个字母少于p，则两个单词之间发生虚假碰撞的概率为1/p。