问题标签 [rabin-karp]

我正在从这里和在线资源中学习子串算法，尤其是 Rabin Karp 子串匹配方法。我看到为了比较较长的子串，我们通常采用模数。

1. 这个K的特点是什么，执行起来更有效？
2. 为什么我们不能比较String mod K和String div K for some K 为什么一旦发生冲突我们必须比较整个字符串？比较 div 和 mod 结果不是比比较字符串更好吗？
3. 我们如何修改用于字符串匹配的 Rabin Karp 算法？现在，我已经实现了一个方法，将每个字符串转换为它的 ASCII 值并存储在一个字符数组中。有一个更好的方法吗？
4. 我了解 Inetegr.parseInt() 是如何 实现的，我看到了 Java 的 String.Contains()。实现此功能时使用什么算法？

谢谢！

例如，我们有 string1:"AB"，它必须在 string2:"CABA" 中找到。对于string1 h1=('A'*27 + 'B') and h2=('A'*29 + 'B')，对于string2我们计算hash1和hash2函数(h2.1='C'*27 + 'A', h2.2='C'*29 + 'C') 我们将结果与 string1 的哈希函数进行比较。

我不明白为什么我们需要 2 个哈希函数，每个字符串或子字符串都有不同的基数。

如何扩展 rabin karp 以在 nxn 个字符中查找 mxm 模式？

任何人都可以想出一个伪代码吗？并且会对算法的时间复杂度有什么影响吗？

有人可以给我一个函数的源代码 -拉宾卡普算法- 在帕斯卡（免费帕斯卡版本）？

我在 Topcoder 阅读 Rabin Karp 算法。但是在那篇文章中，我无法获得以下哈希评估。

它看起来与理论中解释的不同。我知道我可以自由地使用 Rabin Karp 中的任何哈希函数，但仍然要保持教程的流程，我需要解释一下，因为我可能没有正确理解它。

我有一个双重作业问题，实施 Karp-Rabin 并在测试文件和第二部分上运行它：

2. 对于以 q 为模的哈希值，解释为什么使用 q 作为 2 的幂是一个坏主意。你能构造一个糟糕的例子，例如 q=64 和 n=15 吗？

这是我的算法实现：

...问题的第二部分是指代码/算法的这一部分：

我不明白为什么使用 q 作为 2 的幂是个坏主意。我已经尝试在提供的测试文件（这是 ecoli 的基因组）上运行算法并且没有明显的区别。

我尝试查看如何导出哈希的公式（我不擅长数学），试图找到一些对二次幂非常不利的共同因素，但一无所获。我觉得如果 q 是 2 的幂，它应该会导致很多哈希冲突，所以你需要更多地比较字符串，但我也没有找到任何类似的东西。

我真的很感激这方面的帮助，因为我很难过。如果有人想指出我在第一部分可以做得更好（代码效率、可读性、正确性等），我也很高兴听到您对此的意见。

我正在实现 karp-rabin 子字符串匹配算法。当我在子字符串上调用 hash_string() 方法时，我的实现工作正常，但当我实现滚动哈希时失败。我的滚动哈希值不断增长，我不知道为什么。

更具体地说，问题出现在这里：

即使子字符串长度保持不变，滚动哈希值也会增加几个数量级。这种滚动哈希实现是否正确？

我知道 Rabin Karp 对于多个 Pattern 更快，但它应该是相同的长度。但现在我有 10 种不同长度的模式，需要在文本中搜索。它如何运作有效？谢谢！

在通过除以素数将散列减少为模值后，我无法理解滚动散列算法的工作原理。

考虑数字中的 5 位数字序列123456。

第一个块是12345. 我存储值，在下一个窗口中，6 进来，1 出去。

所以新的哈希将是(12345-1*10^4)*10 + 6 = 23456. 这是相当直观的。

很明显，这些数字很大，所以我们需要一个模函数来保持它们很小。假设我101为此目的取素数。

所以12345会减少到23。那么，如何从中得出下一个窗口的滚动哈希23456？

d是字母的大小
T[1...n]是要搜索的文本
P[1...m]是模式（m是模式的大小）
q是一个素数

h = d^m-1 (mod q)是 m 位文本窗口的高位数字“1”的值。

这条线是什么意思？代表什么h？