素数的大小如何影响拉宾·卡普的运行时间？
根据我的理解，用于模数的 P prime 的大小应该是 32\64 位，因此最终的哈希密钥可以在 O(1) 中进行比较。如果我们决定使用大于 m（模式大小）的素数，那么这是否会将我们恢复到 O(mn) 的原始运行时间，因为我们要在 O(m) 中进行 nm 次迭代的比较？
From my understanding, the size of P prime to be used for the modulo should be 32\64 bits so the final hash key can be compared in O(1). if we decide to use a prime, larger than m(size of pattern), would that restore us back to naïve run time of O(mn) since wed be comparing in O(m) for n-m iterations?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
将事情走向极端可能会有所帮助。
假设您的素数 P 是最小的可能素数 2。那么在滚动哈希中只能计算出两个可能的哈希码，因此您预计会在字符串中大约 50% 的索引处看到匹配的哈希值。如果该模式不存在，那么平均运行时间将达到 Θ(mn)。
另一方面，想象一下选择一个对于所有意图和目的而言都是无限的素数 P（例如，其中包含超过 2300 位的素数）。这意味着 P 的修改本质上是无操作，因为滚动哈希永远不会超过 P。在这种情况下，滚动哈希中的位数将大致与模式的长度相同，因此每一步更新滚动哈希的工作量为 Ω(m)，平均净运行时间为 Ω(mn)。
It might help to take things to extremes.
Suppose your prime P is the smallest possible prime, 2. Then there are only two possible hash codes that could be computed in the rolling hash, so you’d expect to see matching hashes at about 50% of the indices in the string. That would take your runtime up to Θ(mn) on average if the pattern never exists.
On the other hand, imagine picking a prime P that is for all intents and purposes infinite (say, a prime with more than 2300 bits in it). That would mean that modding by P would essentially be a no-op, because the rolling hash would never exceed P. In that case, the number of bits in the rolling hash would be roughly on par with the length of the pattern, so the work to update the rolling hash at each step would be Ω(m) for a net runtime of Ω(mn) on average.