问题标签 [rabin-karp]

根据关于 Rabin-Karp 字符串匹配算法的维基百科条目，它可用于同时在字符串中查找几种不同的模式，同时仍保持线性复杂度。很明显，当所有模式的长度相同时，这很容易做到，但我仍然不明白如何在同时搜索不同长度的模式时保持 O(n) 复杂度。有人可以对此有所了解吗？

编辑（2011 年 12 月）：

维基百科文章已经更新，不再声称在 O(n) 中匹配多个不同长度的模式。

我想知道是否有人可以分享 Rabin-Karp 算法的来源？

谢谢

我正在寻找使用滚动散列函数，这样我就可以对一个非常大的字符串的 n-gram 进行散列。

例如：

“stackoverflow”，分成 5 克是：

“stack”、“tacko”、“ackov”、“ckove”、“kover”、“overf”、“verfl”、“erflo”、“rflow”

这对于滚动散列函数是理想的，因为在我计算了第一个 n-gram 散列之后，以下的计算相对便宜，因为我只需删除第一个散列的第一个字母并添加第二个散列的新的最后一个字母.

我知道通常这个哈希函数生成为：

H = c ₁ a ^{k - 1} + c ₂ a ^{k - 2} + c ₃ a ^{k - 3} + ... + c _k a ⁰其中 a 是常数，c1,...,ck 是输入字符。

如果您在Rabin-Karp 字符串搜索算法上点击此链接，它会指出“a”通常是一些大素数。

我希望我的散列存储在 32 位整数中，那么“a”应该有多大的素数，这样我就不会溢出我的整数？

是否存在我已经可以使用的该哈希函数的现有实现？

这是我创建的一个实现：

我使用 101 作为我的素数。我的哈希值是否会溢出有关系吗？我认为这是可取的，但我不确定。

这似乎是解决这个问题的正确方法吗？

我一直在研究 C++ 中的 Rabin-Karp 字符串匹配函数，但没有得到任何结果。我有一种感觉，我没有正确计算某些值，但我不知道是哪一个。

原型

功能实现

在我的函数调用中，我传递 2359023141526739921 作为序列，31415 作为模式，10 作为基数，13 作为素数。我希望有一个实际匹配和一个虚假命中，但我从未从函数的匹配部分获得输出语句。我究竟做错了什么？

提前致谢，麦迪逊

我正在解决一些涉及 Rabin–Karp 字符串搜索算法的问题。该算法要求滚动哈希比简单搜索更快。本文介绍如何实现滚动哈希。我没有问题地实现了“Rabin-Karp rolling hash”，发现很少有实现实现，但文章还提到了计算复杂性，并且首选通过循环多项式对 n-gram 进行散列。它链接到这种技术的BuzHash实现，但我想知道如何使用它在其之上构建 n-gram 哈希。我想要这样的东西或

对于java。

对于会遇到与字符串搜索相关的问题的人（比如我），我发现一些文章很有用：1、2、3

除了 Knuth-Morris-Pratt、Rabin-Karp 等，还有哪些可用的字符串匹配算法？

我一直在尝试用 Java 实现 Rabin-Karp 算法。我很难在恒定时间内计算滚动哈希值。我在http://algs4.cs.princeton.edu/53substring/RabinKarp.java.html找到了一个实现。我仍然无法理解这两条线是如何工作的。

我看了几篇关于模数运算的文章，但没有一篇文章能够穿透我厚厚的头骨。请给出一些指示以理解这一点。

为这个可能重复的问题道歉。

我正在尝试将滚动哈希与 Karp Rabin 一起使用。我查看了滚动哈希的不同实现，我想知道我哪里出错了。尽管文本具有模式，但使用散列的匹配似乎根本没有发生。附加（一部分）用于计算哈希和搜索的代码。

我遇到了缓冲区溢出的问题，我已经处理过了，但是模式和文本哈希似乎与蛋白质序列文本字符串（具有 1000 个字符）和 17 个字符的模式不匹配有什么想法我可能会出错吗？

谢谢， 巴维亚

我之前的问题与一般字符串搜索算法有关。我正在研究 Rabin-Karp 算法，我有一个函数模板，如：

我想知道基数和素数的值将如何根据 search_phrase 和文本变化？还是我应该为所有情况给他们任意值？

我正在使用 Rabin–Karp 算法来检查任何两个源代码文件的抄袭所以首先我简单地在 c# 中实现它的算法，但它的平均和最佳情况运行时间是空间 O(p) 中的 O(n+m) ，但其最坏情况时间为 O(nm)。

那么如何通过使用滚动哈希函数来提高效率，因为这比这更好..