问题标签 [rabin-karp]

问问题

For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.

102 问题

0 投票

3 回答

4832 浏览

string-search - Rabin Karp 什么时候比 KMP 或 Boyer-Moore 更有效？

我正在学习字符串搜索算法并了解它们的工作原理，但还没有找到足够好的答案来说明在哪些情况下 Rabin-Karp 算法会比 KMP 或 Boyer-Moore 更有效。我看到它更容易实现并且不需要相同的开销，但除此之外，我不知道。

那么，Rabin-Karp 什么时候比其他方法更好用呢？

0 投票

1 回答

257 浏览

algorithm - 为什么我们需要在 Rabin Karp 算法中每次哈希值相同时检查模式匹配

我不明白为什么我们需要在每次哈希为模式和文本返回相同值时检查子字符串匹配的原因。对于字符串，返回的哈希值不是唯一的吗？

algorithm hash rabin-karp

0 投票

0 回答

39 浏览

c++ - Robin carp 实施没有给出预期的结果

使用 1000000007 进行散列后，以下代码未提供所需的输出。

使用 101 进行散列可以使其正常工作。你能帮我找出我出错的地方吗？

没有显示输入案例的输出：deeeeeeeeeeeeeeeeeee 和 eeeeeeeeeeee。

c++rabin-karp

0 投票

1 回答

528 浏览

algorithm - C++ 奇怪的结果 - 蛮力比 Rabin-Karp 更快......？

目前正在为一个 uni 模块开发一个字符串搜索程序，并且我已经成功地实现了这些算法，至少到了他们一致地找到字符串的程度。我实现了 Boyer Moore 和 Rabin Karp。当我的一个同学遇到这个确切的问题时，我也投入了蛮力，并意识到我遇到了同样的问题 - 蛮力比单词列表上的 Rabin-Karp 更快。

Rabin-Karp 似乎花费了最多的时间来执行滚动哈希，一开始我很好奇我是否只是有很多碰撞，但我设法用一个巨大的素数将碰撞降低到 3。由于质数的大小，我假设这增加了一点时间，但滚动哈希似乎很明显导致了问题。

这是滚动哈希部分：

我想尝试搜索一个巨大的文本文件，所以我使用了 Rockyou 词汇表，Boyer Moore 对此非常满意，而 Rabin-Karp 只需不到一秒钟的时间。蛮力花费的时间不到 Rabin-Karp 的一半，尽管这对我来说没有意义？

我是否误解了应该如何应用这些算法，或者我正在使用的滚动哈希过程是否存在问题？

algorithm brute-force string-search rabin-karp

0 投票

3 回答

568 浏览

c - O(n) 子串算法

所以我一直在研究子字符串搜索算法，发现大多数算法（如 kmp 和 rabin-karp 算法）在进行一些字符串匹配之前需要额外的时间复杂度来预处理时间。这样做有什么好处吗？为什么他们不直接跳到字符串匹配，以使大 O 时间复杂度不会下降到 O(m+n)？我尝试通过简单地跳过预处理时间来创建一个我认为是 O(n) 的子字符串算法（如果我错了，请纠正我）。我想知道为什么人们不这样做，请参阅下面的 C 代码。

编辑：

删除了 strlen 函数以避免任何不必要的时间复杂度

c algorithm substring knuth-morris-pratt rabin-karp

0 投票

1 回答

41 浏览