问题标签 [rabin-karp]

我正在阅读 CLRS，因为我遇到了这一行“然后我们可以预期虚假命中的数量是 O(n/q)，因为可以估计任意 ts 等于 p，模 q 的机会为 1/q。”

我将包含完整描述的网站放在 34.2 主题下

请解释我们如何预期虚假命中 = O (n/q)

供参考http://staff.ustc.edu.cn/~csli/graduate/algorithms/book6/chap34.htm

我为子字符串搜索编写了一个简单的 Rabin-Karp 算法的逐步实现，它似乎工作正常，直到哈希变得大于模数，然后它出错了......

这是代码，很简单：

问题是，在我取模后，散列可能会变成一个小数，然后，当我向它添加一些大因素时，即使它们应该匹配，散列也可能不匹配。

例如：xabc里面的abc

当我取 abc 和 xab 的哈希值时，假设它们都大于模数，所以在模数运算后它们变小了。

然后，当我删除“x”并添加“c”因子时，总和可以小于模数但仍然很大，所以它不会匹配。

我该如何克服这个问题？

我试图在这里理解 Rabin-Karp 算法：http: //algs4.cs.princeton.edu/53substring/RabinKarp.java.html。

我浏览了各种文章，现在知道多项式哈希的一般形式是 C1*A^k-1+C2*A^k-2+C3*A^k-3。查看代码，我了解它们如何添加和减去字符串中的数字。

txtHash = (txtHash + Q - RM*txt.charAt(i-M) % Q) % Q; txtHash = (txtHash*R + txt.charAt(i)) % Q;

在这里，程序减去前导数字，乘以整个哈希，然后添加新数字。但是，当我查看计算哈希的函数时，它并没有遵循多项式哈希的一般形式。它看起来像这样：

在这个函数中，他们将散列和基数相乘，然后加上 key.charAt()。我认为该函数会将 key.charAt() 与从 R^k-1 开始的基数相乘。然后随着 for 循环的继续，基数将除以 R 以提供多项式中的递减幂。有人可以解释一下这个函数是如何工作的，以及它是如何以我上面提到的形式生成散列的吗？谢谢！

我不知道使用 Rabin Karp 算法进行多模式搜索。我试图在互联网上寻找它。我发现我想要，但不幸的是在 golang 中。如何在 PHP 中使用此代码，或者我可以在 PHP 中使用它吗？

输出

完整代码

在 RK 算法的 Top Coder 代码中：

上面写着

不幸的是，仍有一些情况下，我们必须为文本中的每个起始位置运行“naive”方法的整个内部循环——例如，在字符串“aaaaaaaaaaaaaaaaaaaaaaaa”中搜索模式“aaa”时——所以在在最坏的情况下，我们仍然需要 (n * m) 次迭代。

但是算法不会在第一次迭代本身就停止 - 就像它会看到前三个字母是与针匹配的“a”一样？

我试图理解为什么 Rabin-Karp 算法的最坏情况运行时间是 O(nm) 而平均情况是 O(n+m)。

有人可以帮我吗？

我正在尝试在 f#中实现循环多项式哈希函数。它使用按位运算符 ^^^ 和 <<<。下面是一个散列数组的函数示例：

我的问题是 of 的类型'a将被限制为 a int，而我希望此函数与任何可与按位运算符一起使用的类型一起使用，例如 a char。我尝试使用inline，但这会在我的库中产生一些问题。有没有办法在不使用的情况下解决这个问题inline？

为清楚起见进行编辑：该函数将成为库的一部分，并且为不支持按位运算符的类型提供了另一个哈希函数。我希望这个函数可以处理数字类型和/或字符的数组。

编辑 2（问题已解决）：内联的问题是我从库中加载函数的方式。代替

我使用了这个绑定：

尽管该函数是库中的函数，但它将输入类型限制为myFunctionint 。改变我调用函数的方式修复了类型约束问题，并且工作得很好，如下面的答案所示。createBuzhashinlineinline

我有兴趣实现 Rabin-Karp 算法来搜索子字符串。这是我使用的算法：algorithm。

我为相同的代码如下。但是输出是空白的。它说构建成功但没有输出...

许多重复数据删除库或应用程序应用 Rabin Karp 滚动散列算法进行快速散列以从文件二进制文件中切出一个块。
我的问题是，为什么 Rabin Karp 算法经常用于切割块？
我知道它是快速滚动哈希算法，但我的问题更基本。
有很多方法可以切块。
例如，将一个字节（没有 mod 操作）与切割一个块的值进行比较，平均会产生 256 个字节的块。
比较 9 位将导致平均 512 字节块等。
不只是比较最后几位而没有散列结果类似于 Rabin Karp 等滚动散列算法但更快吗？

在 Rabin Karp 子串搜索算法中：

1) 计算子串的哈希值 2) 取一个滑动窗口[等于子串的大小]，并将窗口中存在的字符串的哈希值与子串的哈希值进行比较。3）如果哈希匹配，那么我们将窗口内容与子字符串进行比较。

问题： 1）首先匹配哈希而不是比较在性能方面有什么好处？为什么我们不能只是比较？比较哈希可以更快但如何（我没有得到）？