根据我的理解，用于模的p素数的大小应该是32\64位，这样就可以在O(1(中比较最终的哈希键。如果我们决定使用一个大于m(模式大小(的素数，这会让我们回到O(mn(的天真运行时吗？因为我们在O(m(中比较n-m次迭代？
将事情推向极端可能会有所帮助。
假设你的素数p是最小可能的素数2。然后，在滚动哈希中只能计算两个可能的哈希代码，因此您可以在字符串中大约50%的索引中看到匹配的哈希。如果该模式永远不存在，那么平均运行时间将达到Θ(mn(。
另一方面，想象选取一个素数p，它在所有意图和目的上都是无限的(比如说，一个素数中有超过2300个比特(。这意味着，用P进行修改本质上是一种无操作，因为滚动哈希永远不会超过P。在这种情况下，滚动哈希中的位数将与模式的长度大致相等，因此在平均Ω(mn(的净运行时间内，每一步更新滚动哈希的工作将是Ω(m(。