我正在使用递归公式研究 Rabin Karp 算法。以下是代码。在代码中，我正在检查以正常方式和递归公式计算的哈希值。两个值都不匹配。我花了将近 3 个小时的时间进行调试，不知道是什么问题。请求您帮助查找错误。

预期答案是：1 2 3

我正在尝试用 mod 实现 Rabin Karp 算法。我正在使用的哈希函数是：

这里 cx 是字符的 ASCII 值。为了滚动它，我首先通过减去它来删除第一项，然后乘以 a 并通过将它乘以 a^0 来添加新项。

现在的问题是处理我使用过 mod 操作的大值，但这样做我无法正确滚动它。我的代码如下：

问题是，textHash在patternHash任何时候都不匹配。我确信问题出在 mod 操作上。任何人都可以告诉如何拥有 mod 以及正确使用滚动哈希。我将非常感谢。

来自https://algs4.cs.princeton.edu/53substring/

15. 最长回文子串。给定一个字符串 s，找出最长的子串，它是一个回文（或 Watson-crick 回文）。

解决方案：可以使用后缀树或 Manacher 算法在线性时间内求解。这是一个更简单的解决方案，通常在线性时间内运行。首先，我们描述如何在线性时间内找到长度正好为 L 的所有回文子串：使用 Karp-Rabin 迭代地形成每个长度为 L 的子串（及其反向）的哈希值，并进行比较。因为你不知道 L，所以重复你对 L 的猜测，直到你知道最佳长度在 L 和 2L 之间。然后使用二进制搜索找到确切的长度。

我不明白的是最后一部分。

因为你不知道 L，所以重复你对 L 的猜测，直到你知道最佳长度在 L 和 2L 之间。

我怎么知道“最佳”长度是多少？

PS：最长回文子串的问题之前已经问过，但似乎唯一有用的是this，它也没有使用Rabin-Karp。

编辑：这是我根据收到的答案提出的代码。

func 使用 hash_formula 计算模式的哈希值和文本大小为 m 的初始幻灯片

使用先前计算的计算下一个哈希值的函数

输出#1：

输出 #2：未检测到

输出#3：检测到

输出#4：未检测到

我无法弄清楚为什么会这样。我认为在某些情况下，通过滚动散列函数从先前存储的散列值计算的散列值不等于该文本大小（m）的实际散列值。我在哪里做错了？

提前致谢

下图来自： 6.006-算法简介，

在学习 MIT OCW 提供的 6.006-Introduction to algorithm 课程时，我遇到了 Rabin-Karp 算法。

谁能帮我理解为什么需要第一个 rs()==rt() ？如果使用了，那我们是不是也应该先通过蛮力检查字符串是否相等，然后继续前进？为什么在从 t[0] 进行散列然后尝试查找其他字符串匹配时我们不考虑字符串的相等性？

在图像中，rs() 用于哈希值，rs.skip[arg] 用于删除该字符串的第一个字符，假设它是'arg'</p>

这个问题与rolling-hash非常相似，但是关于溢出/否定结果的一些细节对我来说仍然不清楚。

我也检查了这个 Rabin-Karp实现，并且对下面的行有疑问：

我了解以下表达式可能会给出否定结果：

第一个问题：

• 如果我们总是添加 Q，一个大素数，这个结果是否会由于溢出而导致负数？
  • 如果不是，为什么不呢？如果是，是否应该仅在结果为负时才进行此添加？

第二个问题：

如果我们暂时不关心负数，写下面的表达式是否正确？

第三个问题，这部分最让我困惑：

让我们假设当我们添加 Q 时不会发生溢出。为什么在前导数字上有最左边的 % Q 操作？

我已经阅读了我链接的答案，并根据 Aneesh 的答案，如果我理解正确，下面的表达式应该是相似的：

但我不明白为什么它们相似，因为在哈希示例中，% p 不是针对先前的哈希值计算的，但是对于 txtHash，我们也计算了先前哈希的 % Q。

我正在阅读 Wikipedia 上的Rabin-Karp算法，其中提到的时间复杂度为 O(n+m)。现在，根据我的理解，m 必然在 0 和 n 之间，所以在最好的情况下复杂度是 O(n)，在最坏的情况下也是 O(2n)=O(n)，那为什么不是只是 O(n)？

我一直在阅读Rabin Karp算法Introduction To Algorithms。除以下内容外，一切都有意义。

我不明白什么是 a以及在该算法的上下文中computer word拟合的意义是什么。dq within a computer word

我在某处读到它与单精度数学有关，但我也不明白single-precision math。

任何人都可以分解这些术语吗？谢谢你。

我正在研究一种代码剽窃检测方法。我需要为这种方法使用指纹算法。指纹算法将源代码的所有子串放到一个哈希表中。（所有子串长度相同。）为了优化，建议在将指纹放入哈希表时使用Rabin-Karp算法。

例如; 对于 string = abcdef和 length = 5，我们应该将abcde和bcdef子字符串放入哈希表。由于字符串的散列需要对字符串的每个字符应用数学运算，因此对于大量子字符串来说会很昂贵。

Rabin-Karp 算法利用子串的连续性。它计算第一个指纹的哈希值。对于其余的子字符串，它使用前一个子字符串。

C++ 的“映射”容器是否会自动将此算法应用于背景上的连续子字符串？还是我应该编写自己的哈希库？

我想我在概念上理解使用滚动哈希的 RabinKarp 模式匹配算法。在这里通过示例实现时，我发现一个大素数q被添加到先前计算的滚动哈希中。

我不确定为什么需要这样做。我能得到一些帮助吗？

在我有限的测试中，无论是否q包含术语，我都会得到相同的结果。

这是否与正在实施的算法版本（蒙特卡洛/拉斯维加斯）有关？