问题标签 [rabin-karp]

这是 C# 中 Rabin-Karp 字符串匹配算法的实现......

}

但是如果我更改第二个字符串的位置而不是显示结果未复制但它有一个问题

这里显示未复制

我想检查它是否是从第一个字符串复制的，甚至我会在其中添加一些内容或更改位置，但它不应该有所不同，所以如何更改它，它只会比较字符串中每个单词的哈希值而不是执行它…………

我正在阅读 Cormen 等人的算法简介中的字符串算法

以下是关于一些基本数论符号的文本。

注意：在下面的文本中，将 == 引用为模等价。

给定一个整数除以另一个整数的余数的定义明确的概念，提供特殊符号来表示余数相等是很方便的。如果 (a mod n) = (b mod n)，我们写 a == b (mod n) 并说 a 等价于 b，模 n。换句话说，如果 a 和 b 除以 n 时具有相同的余数，则 a == b (mod n)。等效地，a == b (mod n) 当且仅当 n | (b-a)。例如，61 == 6（模 11）。此外，-13 == 22 == 2 == (mod 5)。

整数可以根据余数模n分为n个等价类。包含整数 a 的等价类模 n 是

[a]n = {a + kn : k Z} 。

例如，[3]7 = {。. . , -11, -4, 3, 10, 17, . . .}; 该集合的其他表示是 [-4]7 和 [10]7。

写 a 属于 [b]n 与写 a == b (mod n) 相同。所有这些等价类的集合是

Zn = {[a]n : 0 <= a <= n - 1}.---------> 等式 1

我在上面的文字中的问题是在等式1中提到“a”应该在0和n-1之间，但在示例中它被给出为-4，它不在0和6之间，为什么？

除了上面提到的，对于 Rabin-Karp 算法，我们使用两个数模第三个数的等价性？这是什么意思？

我正在阅读 Cormen 的算法简介等的 Rabin-Karp 算法。

www.cs.uml.edu/~kdaniels/courses/ALG_503_F08/503_lecture11.ppt

注意这里 == 用作 mod 运算符

以上幻灯片 13 上的注释，即 Eq 34.2，作为图片附在此处。在等式中，我们有 h == (d)powerof((m-1) (mod q) 是 m 位文本窗口的高阶位置中的数字“1”的值。

我在这里的问题是作者所说的“在 m 位文本窗口的高位位置中的数字“1”的值”是什么意思？

在幻灯片 14 上，作者如何得到 (7-3.3).10 + 2 (mod 13) 为 8 (mod 13)？

在平均案例分析中提到，我们可以基于以下假设进行启发式分析：减少模 q 的值就像从 sigma* 到 Z 的随机映射。这里作者的上述陈述是什么意思？

我一直在研究一个使用MOSS的 Idea 的小型抄袭检测引擎。我需要一个滚动哈希函数，我的灵感来自 Rabin-Karp 算法。

我写的代码 -->

我正在使用值运行它-> calc_hash(text,5,101) 其中文本是字符串输入。

代码非常慢。我哪里错了？

注意：很多可能的重复项，但似乎没有解决我的问题。

我正在研究基于MOSS的抄袭检测。

在成功实现一个过滤器去除所有必要的细节（评论、标点符号等）后，我使用滚动哈希实现（Rabin Karp）对内容进行哈希处理

然而，在源代码的两个文本文件中匹配的哈希具有非常不同的底层文本（没有抄袭但相同的哈希）

我实现的算法（Ruby）->（部分片段）

我的实施有问题吗？或者我指定的参数可能有问题？

我取 radix=34 （我不确定它是否是正确的值，我假设删除的文本将只包含字母+一些特殊字符，如 '+'、'-'、'*'、'/' 所以粗略估计总共 34 个字符）

我将 q(prime) 设为 101

这是我正在处理的碰撞问题吗？关于如何解决问题的任何指示？

几周前，我向 Stackoverflow 提出了一个关于创建一种高效算法来搜索大量文本中的模式的问题。现在我正在使用字符串函数 indexOf 进行搜索。一个建议是使用 Rabin-Karp 作为替代方案。我编写了一个如下的小测试程序来测试 Rabin-Karp 的实现，如下所示。

这是我正在使用的 Rabin-Karp 的实现：

Rabin-Karp 的实现可以返回我正在寻找的字符串的正确偏移量。但令我惊讶的是我运行测试程序时发生的时间统计。他们来了：

这真是令人惊讶。Rabin-Karp（至少在这里实现）不仅不比标准的 java indexOf String 函数快，而且慢了一个数量级。我不知道出了什么问题（如果有的话）。有人对此有想法吗？

谢谢，

艾略特

您好我正在编写一个 PHP 类来实现 Rabin-Karp 算法。我对重新散列部分有疑问。此代码不包括匹配的部分字符。我不得不停下来，因为由于重新散列的问题，它从不匹配散列码。有人请帮我弄清楚。

谢谢你。

我有兴趣实现 Rabin-Karp 算法来搜索 wiki 上所述的子字符串：http ://en.wikipedia.org/wiki/Rabin-Karp_string_search_algorithm 。不是为了功课，而是为了自己的利益。我已经实现了 Rabin-Karp 算法（如下所示）并且它有效。但是，性能真的，真的很差！！！我知道我的哈希函数是基本的。但是，似乎对 strstr() 的简单调用总是会胜过我的函数 rabin_karp()。我可以理解为什么 - 哈希函数比简单的逐个字符比较每个循环所做的工作更多。我在这里想念什么？Rabin-Karp 算法是否应该比调用 strstr() 更快？什么时候最好使用 Rabin-Karp 算法？因此我的个人利益。我什至实现了算法吗？

我在网站上的论坛中看到了这个 Rabin Karp 字符串匹配算法，我有兴趣尝试实现它，但我想知道是否有人能告诉我为什么变量 ulong Q 和 ulong D 分别为 100007 和 256：S ? 这些价值观有什么意义？

我编写了 ac 程序，该程序应该使用Rabin Karp 算法将文件切成块。这是您可以在此处找到的 ac# 程序的改编版本。

它似乎有效，但仍然存在问题。平均块大小不是预期的。

用法如下：

rabin Prime WindowSize 边界标记文件

在哪里 ：

Rabin 是可执行文件的名称。

素数是一个高素数。例如 100007

WindowSize 是滚动窗口的大小。例如 48

BoundaryMarker 是指纹中设置为 0 的位数

文件是要处理的文件

如果我将 BoundaryMarker 设置为 13，我希望平均块大小为 8K。事实上，它们都不在 8K 左右。

我很难弄清楚我的程序出了什么问题？你能帮助我吗 ？

谢谢