我无法理解为什么Rabin-Karp 算法的平均案例运行时间为O(n+m)，其中 n 是输入字符串的长度，m 是模式字符串的长度。我的理解是所有 n 和 m 的运行时间应该是 O(n+m)，即使 n 和 m 非常大。
让我们的散列函数返回 1 到 k 之间的整数。那么在每个位置发生虚假碰撞的概率为 1/k，因此我们期望平均得到 O(n/k) 次虚假碰撞以及一个正确的哈希匹配（如果存在匹配）。因此，我们期望 O(1+n/k) 散列匹配。每次我们得到一个匹配，我们必须检查平均 O(m) 个字符，所以总平均运行时间是 O((1+n/k)*m)。
对于小的 n (n<<k)，这近似于通常引用的平均运行时复杂度 O(n+m)。但是对于大的 n (n>>k)，它是 O(n/k m)=O(n m)。所以对于大的 n，平均运行时间复杂度是 O(n m)，这意味着理论上平均运行时间是 O(n m)，而不是 O(n+m)。但是当然，我们通常处于 n<<k 的范围内，因此我们可以期望在实践中对于短字符串 O(n+m)。
如果我们试图绕过碰撞问题，通过随着 n 变大调整 k 以保持较低的碰撞率恒定，那么 k 将需要 O(n)。但是对于大的 n，算法仍然是 O(n m)，因为对模式字符串进行哈希处理将需要 O(k m)=O(n*m)。
我的问题是，这个分析的缺陷在哪里？理论上，Rabin-Karp 实际上是平均情况 O(n*m) 吗？我错过了什么？