Rabin Karp Algorithm in Data Structure And Algorithm : Practice MCQ Questions & Answers with Explanations

Rabin-Karp algorithm was invented by Richard Karp and Michael Rabin in 1987 for pattern searching in strings.

Rabin-Karp uses hashing. Every substring of the text is converted to a hash value and compared with the hash value of the pattern for fast matching.

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).

If q is large enough, spurious hits occur infrequently, making the cost of extra checking low.

Since Rabin-Karp is a pattern detection algorithm, it can be applied to detect plagiarism by searching for matching text patterns across documents.

The worst case running time is Theta((n-m+1)m). We write n-m+1 instead of n-m because there are n-m+1 different positions the pattern can start in the text.

Horner's rule is used to evaluate the pattern in Theta(m): p = P[m] + 10(P[m-1] + 10(P[m-2] + ... + 10(P[2] + 10P[1])...)).

Rabin-Karp Algorithm uses elementary number theoretic notions such as the equivalence of two numbers modulo a third number.

The for loop in the pre-processing step runs m times (length of the pattern). Hence the pre-processing time is Theta(m).

Rabin-Karp is a string matching algorithm proposed by Rabin and Karp. It generalizes to other algorithms and also applies to two-dimensional pattern matching problems.