问题标签 [rabin-karp]

我一直在尝试构建 Rabin-Karp，并且我理解登录以下代码是相同的结果。gfg 文章中的代码看起来是一样的，只是我使用了一个循环而不是两个循环，并且哈希函数有一点变化。

你能帮我解决这个问题吗？

关于 gfg 文章的代码

我认为这两种逻辑几乎相同。如果我错过了什么，请告诉我。

使用 Rabin-Karp 方法进行字符串匹配，该方法使用了多少个字符-字符匹配？在哪里：

所以我正在解决这个问题（Rabin Karp 算法）并编写了这个解决方案：

现在，如果 mod = 1000000007，这段代码根本不起作用，而只要我们取一些其他素数（足够大，比如 1e5+7），代码就会神奇地开始工作！

代码逻辑失败的行是：

有人可以告诉我为什么会这样吗？？？也许这是一个愚蠢的疑问，但我就是不明白。

我已经在 python 中实现了用于模式搜索的 Rabin-Karp 2D 算法。但是，我的实现比 1000x2000 矩阵上的蛮力版本慢。请帮我识别瓶颈。谢谢，我很欣赏你的评论。

注意 1：代码在找到模式匹配但运行速度较慢的位置时是正确的，我的计算机上的蛮力版本为 1.23 秒与 0.54 秒。

注意 2：尽管可以提出最坏的情况，使得 Rabin-Karp 可能像蛮力一样慢，但给出的测试用例并不是故意设计成 O(m(n-m+1))。

免责声明：虽然这个问题是 Sedgewick 和 Wayne 的 Algorithms, 4th Edition 中的一个分配问题，但这不是我的作业。我正在学习这个算法。

这是代码：

我在 Rabin-Karp 算法中了解以下内容

h=d^m-1 但我不明白我们为什么要写

在代码中

我知道 Rabin-Karp 字符串匹配算法是如何工作的，但无法理解它比本机方法更好。在 Rabin-Karp 中，您可以找到字符串中每个子字符串的哈希值，并将其与测试字符串的哈希值进行比较。如果匹配，您现在比较各个字符。但是在本机方法中，您只需将子字符串与测试字符串字符进行比较按性格。计算哈希不是不必要的吗？它比比较单个字符更快吗？

我试图了解 Rabin-Karp 算法的实现。d 是输入字母表中的字符数，但如果我替换 0 或任何其他值而不是 20，它不会影响任何内容。为什么会这样？

我有这个 Rabin Karp 实现。现在我为滚动哈希做的唯一事情就是power*source[i]从sourceHash. power是31^target.size()-1 % mod 但我不明白为什么我们要mod在sourceHash它变成负数时添加。我尝试添加其他值，但它不起作用，它仅在我们添加mod. 为什么是这样？是否有特定原因为什么我们要添加mod而不是其他任何内容（例如随机大数字）。

我想实现一个问题解决方案，该解决方案需要一个散列函数，该函数为相似的输入返回相同的输出。输入将是一些代码，我希望散列函数忽略变量名称等。

如果没有这样的散列函数可用，那么我如何使用其他散列算法来实现它。请问有什么建议吗？

我目前正在阅读 Rabin Karp 算法，作为其中的一部分，我需要了解字符串多项式哈希。据我了解，字符串的哈希值由以下公式给出：

在哪里：

• char_i_val：是字符的整数值加 1string[i]-'a' + 1
• p 是大于字符集的素数
• m 是一个大素数

网站 cp-algorithms 有以下关于该主题的条目。他们说写上面的代码如下：

我理解程序试图做什么，但我不明白为什么它是正确的。

我的问题

我无法理解为什么上面的代码是正确的。自从我做任何模块化数学以来已经有很长时间了。在网上搜索后，我看到我们有以下模加和模乘的公式：

基于以上内容，代码不应该如下吗？

我错过了什么？理想情况下，我正在寻求代码的细分以及为什么第一个版本是正确的解释。