问题标签 [rabin-karp]

我正在为 Rabin-Karp 算法寻找一个有效的哈希函数。这是我的实际代码（C 编程语言）。

我考虑了一些 Rabin-Karp C 实现，但所有代码之间存在差异。所以我的问题是：Rabin-Karp 哈希函数应该具有哪些特征？

有哪些好的散列函数可用于实现Rabin-Karp 字符串搜索算法？我只知道多项式散列，但它有一些缺陷——最值得注意的是，如果散列是以 ​​2 ⁶⁴为模完成的，则有一个测试可以保证经常产生冲突（并且使用另一个模数是不切实际的，因为mod操作非常昂贵） . 那么，有没有一个快速、易于编写的好哈希函数呢？

PS 我知道 buzhash，但我想知道是否还有其他选择......</p>

所以我是 Haskell 的新手，我必须编写 Rabin Karps 算法。我觉得我的答案应该有效，但是我在编译时不断收到“'let' 上的解析错误”错误。谁能帮帮我。

这是我的代码：

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

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

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

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

我从那个站点找到了一个 rabin karp 代码并改为尝试。修改后的代码如下。您可以在 hashtable.txt 中查看单词及其哈希值。对于下面的示例 hashtable.txt 似乎是正确的。

但是当我将 M（块长度）更改为 150 时，我得到了错误的结果。例如，在 hashtable.txt 中，第一行和第六行必须相同，但它们的哈希值不同。

或者当我将 q （质数）更改为 683303 时，它也会得到错误的结果。

rabin karp算法中素数和块长度之间的关系是什么，错误结果的原因是什么？

我构建了一个函数，它基于 Rabin–Karp 算法按升序查找两个文本文件的最长公共子字符串。主要功能是“find_longest”，内部功能是：“make_hashtable”、“extend_fingerprints”和“has_match”。我无法分析has_match的平均案例复杂度。

将 n1,n2 表示为 text1,text2，将 l 表示为当前“窗口”的大小。finger 是子串的哈希表。

这是“make_hashtable”，在这里我很确定复杂度是 O(n2-l+1)：

这是“find_longest”，我添加了这个函数，尽管我不需要它来进行复杂性分析。

这是“extend_fingerprints”：

我对这两个选项有疑问：

1.O(n_2-l+1)+O(n_1-l+1)*O(l) 将 r 称为常数，而 n1,n2 非常大，因此在哈希表中会发生很多冲突（假设每个“单元格”的 O(1) 项，但是，总是有一些“误报” ")

2.O(n_2-l+1)+O(n_1-l+1)+O(l)
将 r 称为最佳哈希函数，因此几乎没有冲突，这意味着如果两个文本是哈希表中的相同单元格，我们可以假设它们实际上是相同的文本？

我个人倾向于 Bold 声明。tnx。

我一直在尝试理解算法类的 Rabin-Karp 算法。我在理解它时遇到了很多麻烦，所以我尝试实现它（我实际上不必实现它）。我想我正确理解了除了滚动哈希函数之外的所有内容。我的算法目前仅在模式 char[] 与文本 char[] 的开头匹配时才有效。我无法弄清楚我的滚动哈希哪里出错了。如果有人可以请指出错误的方向，我会非常感激。

结果文本“我的测试字符串”模式“我的” - 这作为匹配模式“测试” - 这表明不匹配

在 Coursera 视频之一中，Rabin-Karp 滚动哈希 ( http://en.wikipedia.org/wiki/Rolling_hash ) 显示为：

我认为这是错误的。我认为应该是：

哪一个是正确的，为什么？

我已经在 C#.NET 中实现了 Rabin-Karp 算法，遵循这个伪代码：

问题是，模式与原始文本不匹配。我已经彻底浏览了代码，但我无法识别代码中的问题。有人可以告诉我代码中的错误吗？

我使用以下字母生成了一个字符串。 {A,C,G,T}. 我的字符串包含超过 10000 个字符。我正在其中搜索以下模式。

• ATGGA
• TGGAC
• CCGT

我已要求使用具有O(m+n)运行时间的字符串匹配算法。

两者KMP and Rabin-Karp algorithms都有这个运行时间。在这种情况下，最合适的算法（在 Rabin-Carp 和 KMP 之间）是什么？