Loading practice questions
If the expected number of valid shifts is small and modulus is larger than the pattern length, what is the matching time of the Rabin-Karp Algorithm?
Correct Answer: B — O(n+m)
Explanation:
When the number of valid shifts v is O(1) and q >= m, the matching time O(n) + O(m(v + n/q)) simplifies to O(n+m).