问题标签 [rabin-karp]

我无法理解为什么Rabin-Karp 算法的平均案例运行时间为O(n+m)，其中 n 是输入字符串的长度，m 是模式字符串的长度。我的理解是所有 n 和 m 的运行时间应该是 O(n+m)，即使 n 和 m 非常大。

让我们的散列函数返回 1 到 k 之间的整数。那么在每个位置发生虚假碰撞的概率为 1/k，因此我们期望平均得到 O(n/k) 次虚假碰撞以及一个正确的哈希匹配（如果存在匹配）。因此，我们期望 O(1+n/k) 散列匹配。每次我们得到一个匹配，我们必须检查平均 O(m) 个字符，所以总平均运行时间是 O((1+n/k)*m)。

对于小的 n (n<<k)，这近似于通常引用的平均运行时复杂度 O(n+m)。但是对于大的 n (n>>k)，它是 O(n/k m)=O(n m)。所以对于大的 n，平均运行时间复杂度是 O(n m)，这意味着理论上平均运行时间是 O(n m)，而不是 O(n+m)。但是当然，我们通常处于 n<<k 的范围内，因此我们可以期望在实践中对于短字符串 O(n+m)。

如果我们试图绕过碰撞问题，通过随着 n 变大调整 k 以保持较低的碰撞率恒定，那么 k 将需要 O(n)。但是对于大的 n，算法仍然是 O(n m)，因为对模式字符串进行哈希处理将需要 O(k m)=O(n*m)。

我的问题是，这个分析的缺陷在哪里？理论上，Rabin-Karp 实际上是平均情况 O(n*m) 吗？我错过了什么？

在过去的几天里，我一直在研究拉宾指纹。虽然总体思路很简单，但我在理解网络上流传的实现时遇到了很大的麻烦。特别是它们似乎都源自原始的LBFS 论文，即来自librabinpoly的滑动窗口定义为：

U/T 表是从初始多项式生成的。我没有在任何有关 rabin 指纹识别的论文中看到讨论这两个表的用法和 XOR 操作。我的直觉是这与模运算有关，但我不完全确定。Git 的源代码也使用 rabin 指纹识别，但它们不是动态地派生表，而是使用一组预先计算的表。所以我的问题是 - 这些 Xor 操作究竟能实现什么，并且代码通常看起来与算法的“规范”解释完全不同

我正在阅读 Sedgewick 的 Rabin-Karb 算法。书上说：

我们使用随机素数 Q 取尽可能大的值，同时避免溢出

在第一次阅读时，我没有注意到随机的重要性，当我看到代码long中使用了 a 时，我的第一个想法是：
a）使用 Eratosthene 的筛子找到适合 along
或
b）从列表中查找质数任何足够大且大于的质数int并将其用作常数。

但是其余的解释说：

我们将使用一个long大于10^20使发生碰撞的概率小于的值10^-20

这部分让我感到困惑，因为 along不适合10^20更不用说大于那个值了。然后，当我检查素数的计算时，这本书遵循了一个只有以下提示的练习：

一个随机的 n 位数是质数，概率与 1/n 成正比

这意味着什么？

所以基本上我没有得到的是：
a）使用随机素数是什么意思？为什么我们不能预先计算它并将其用作常数？
b）为什么10^20提到它，因为它超出了范围long？
c) 这个提示有什么帮助？究竟是什么意思？

我正在解决Leetcode 1044，答案是使用二进制搜索和滚动哈希。基本上使用二进制搜索来选择一个长度，然后搜索该长度的重复字符串。这里滚动散列发挥作用以节省空间（我们存储子字符串的散列而不是使用集合来存储所有子字符串）。这就是解决方案的背景。

我的问题是关于用于防止溢出的模数。我选择了 Long.MAX_VALUE，我认为它足够大，可以处理它，但是当我使用 Long.MAX_VALUE 时答案不正确。但是，当我使用 Long.MAX_VALUE / 26 或 Math.pow(2, 32) 时，它们都可以工作。抱歉，我对模数不太了解，我想我肯定在这里错过了一些东西。任何人都可以对此有所了解吗？谢谢！以下是我的解决方案：

我已经开始学习字符串处理算法，并想在 C++ 中实现 Rabin-Karp 算法。我采取了：

p = 大于字符集的素数：31 m = 模运算的素数：1e9+9

根据我能找到的，有多种实现算法的方法，我已经测试了其中两种：随着我们进入更高的索引而增加功率，以及随着我们进入更高的索引而降低功率。

例如在字符串 S[0..n-1]

令 M1 = S[0]*p^0 + S[1]*p^1 + S[2]*p^2 + ... + S[n-1]*p^n-1

令 M2 = S[0]*p^n-1 + S[1]*p^n-2 + S[2]*p^n-3 ... + S[n-1]*p^0

我已经实现了这两种方法，并且只能使用 M2 获得成功的结果。

M1 的代码：

M2 的代码：

测试输入：字符串 s = foobarfoo 字符串 t = barfoobarfoobarfoobarfoobarfoobarfoo

我在 M2 上得到了正确的结果，但在 M1 上没有。

这已经被问了很多，但我有一个场景，如果向量大小已知并且字符或整数中没有重复怎么办？

认为：

我们已经知道我将有最多 10 个整数并且没有重复。我有很多向量要计算，但可以说这是最大尺寸为 10 的最坏情况。
论坛：

显然 PRIME_BASE 应该是 = vector size - 1 在这种情况下是 9 （我知道 9 不是素数基数）但它不会产生冲突。

但是如何选择 PRIME_MOD 来减少在知道向量的最大大小并且其中没有数字重复的情况下生成的大数字？
我正在尝试生成线性同余哈希。

谢谢

更新
我也忘了提到我们已经知道所有向量中的最大数字也是已知的，在这个示例中是 10。

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

我已经按照 MIT course 6006 实现了这段代码。我在上面的代码中使用了一些标记来查看时间。我将其更改match.txt为许多不同的大小以及desirable变量，这是我想在文档中找到的那个。但是对于很多变体，链接中描述的朴素算法总是更快。我选择 89 作为素数。代码基于此链接：

https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/MIT6_006F11_lec09_orig.pdf

我需要一些关于我的 Karp-Rabin 算法的特定部分的帮助。我想要做的是用固定sliding window和单独append的skip部分来实现版本。Sliding window工作得很好。当我尝试将整体拆分为sliding window多个append部分时，就会出现问题skip。Append似乎工作正常，但这skip是过去几天让我头疼的事情。

问题- 我正在滑过包含几个订阅模式实例的字符串。Sliding window检测到它，但没有检测到其他两个。

这个想法是该结构保存（base ^ window size）mod prime number（ ）RH的预先计算值，因此我可以删除字符串的前导字符。这个值毕竟会随着窗口大小的变化而变化。为了减小 的值，乘法逆用于不处于模删除的情况（基模模值的逆）。它也是预先计算的。b2wmodappendskipb2wmod

以下是我感兴趣的代码部分。我不发布整个代码以免您阅读所有内容，但如果需要可以上传。乘法逆似乎计算正确，但我也可以上传代码。

将不胜感激任何帮助！先感谢您！

我了解 rabin-karp 算法及其在字符串搜索中的用法。我不太明白的是它如何动态地将文件分割成可变长度的块。据说在每个字节偏移处计算一个小数据字节窗口（例如：48 字节）的散列，并且当散列的最后 N（例如：13）位为零时，块边界（称为断点）是零。这为您提供了 2^N = 2^13 = 8192 = 8 KB 的平均块大小。问题：

1. rabin-karp 滚动哈希是否从前 48 个字节开始，然后每次滚动一个字节。
2. 如果是这样，即使使用简单的哈希函数来计算大文件是否太多？
3. 给定不可预测的数据，如何在大块大小限制内使散列的 N 位为零？